Java algorithme de Floyd
Discutez d'informatique ici !
-
joridder
- Membre Naturel
- Messages: 56
- Enregistré le: 30 Juin 2006, 15:54
par joridder » 03 Mai 2009, 19:48
Bonjour!
J'aurai besoin de votre précieuse aide pour recoder l'algorithme de Floyd ci dessous (en procédural), en utilisant les "objets".
Cet algo détermine le plus court chemin entre tout couple de points parmi n, et ressort une matrice p après les k incrémentations (k<n)
Je débute en java et ceci est dans le cadre d'un projet d'info.
Je vous remercie d'avance.
- Code: Tout sélectionner
class Floyd {
static final int M=Integer.MAX_VALUE;
public static int[][] floyd(int[][]z){
int n = z.length;
int[][]p=new int[n][n];
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(z[i][j]!=M){p[i][j]=i;}
if(z[i][j]==M){p[i][j]=M;}
}
}
int[][]x=new int[n][n];
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
x[i][j]=z[i][j];
}
}
for(int k=0;k<n;k++){
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(x[i][k]==M||x[k][j]==M continue;
int u=x[i][k]+x[k][j];
if(u<x[i][j]){
x[i][j]=u;
p[i][j]=p[k][j];
};
}
}
}
return p;
}
}
-
fatal_error
- Modérateur
- Messages: 6610
- Enregistré le: 22 Nov 2007, 14:00
par fatal_error » 03 Mai 2009, 21:25
Salut,
- Code: Tout sélectionner
public class Floyd {
static final int M = Integer.MAX_VALUE; // M, tout a fait.
public static int[][] floyd(int[][]z){
/* floyd. Quel joli nom pour une methode. Mais que fait-elle? */
int n = z.length;
int[][]p=new int[n][n];
//quel est le but du double bloc?
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(z[i][j]!=M){p[i][j]=i;}
if(z[i][j]==M){p[i][j]=M;}
}
}
//quel est le but du double bloc?
int[][]x=new int[n][n];
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
x[i][j]=z[i][j];
}
}
//wow, quel est le but du triple bloc?
for(int k=0;k<n;k++){
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(x[i][k]==M||x[k][j]==M) continue;
int u=x[i][k]+x[k][j];
if(u<x[i][j]){
x[i][j]=u;
p[i][j]=p[k][j];
}; // pas besoin de ;
}
}
}
return p;
}
}
Tu as bien précisé ce qu'elle retourne, mais ca faut y mettre dans le code en commentaires...
Si tu arrives a repondre aux quelques questions, je pense que tu pourras procéder par procédures.
la vie est une fête

Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 1 invité