Dijkstra

Bonsoir,

Pouvez vous m'aider dans l'implémentation de l'algorithme de Dijkstra (en Java). J'ai déjà commencé le travail mais je bloque sur l'affichage de la distance du plus cours chemin entre deux noeuds du graphe.




public class InputGraph {

public int [][] arc; // Matrice d'adjacense
public Object [] sommet; //objet sommet

public static int count;

public InputGraph (int n){
arc = new int[n][n];
sommet = new Object[n];

}
public int GetSize (){ // récupère la taille du sommet
return sommet.length;

}

public void SetSommet(int node, Object label){ //permet d'ajouter un sommet
sommet[node]=label;

}

public Object GetSommet(int node){ // récupère la valeur d'un sommet
return sommet[node];

}


public void AddArc(int SommetDep, int SommetArr, int dist){ // ajoute un arc
arc [SommetDep][SommetArr]=dist;

}

public int GetPoids(int SommetDep, int SommetArr){ //récupère la distance
return arc [SommetDep][SommetArr];

}




public void AfficheMatrice(){ //affiche la matrice du graphe

for (int j = 0; j < arc.length; j++) {
System.out.println("");
System.out.println( " DE " + sommet[j] +" jusqu'à ");
System.out.println("");
for (int i = 0; i < arc[j].length; i++) {
if (arc[j][i]>0)
System.out.println(sommet[i] + " la distance est de " +arc[j][i] );
}
}

}
public int [] ChercheVoisin(int node){ //construit un tableau des sommets adjacents d'un sommet

count=0;

for (int i = 0; i < arc[node].length; i++) {
if (arc[node][i]>0 ) {count ++; }
}
final int[]rep = new int [count];

count=0;
for (int i = 0; i < arc[node].length; i++){
if(arc[node][i]>0){rep[count++]=i;}
}
return rep;
}

public static void main(String[] args) {

InputGraph ex = new InputGraph (4);
ex.SetSommet(0, "processus");
ex.SetSommet(1, "phase");
ex.SetSommet(2, "activité");
ex.SetSommet(3, "label");
ex.AddArc(0, 1, 400);
ex.AddArc(0, 2, 200);
ex.AddArc(1, 2, 300);
ex.AddArc(2, 1, 100);
ex.AddArc(1, 3, 100);
ex.AddArc(2, 3, 500);
ex.AddArc(2, 0, 200);

ex.AfficheMatrice();


}
}
==========================================================

public class Dijkstra {


public static int [] djikstra (InputGraph IG, int Source){

final int [] distancecc = new int [IG.GetSize()];
final int [] pred = new int [IG.GetSize()];
final boolean [] marque = new boolean [IG.GetSize()];

for (int i = 0; i < distancecc.length; i++) {
distancecc[i]=Integer.MAX_VALUE;
}
distancecc[Source]=0;

for (int i = 0; i < distancecc.length; i++) {

final int U=ExtraireMin (distancecc, marque);
marque[U]=true;

final int [] V= IG.ChercheVoisin(U);
for (int j = 0; j < V.length; j++) {
final int NV = V [j];
final int d = distancecc[U] + IG.GetPoids(U, NV);
if (d < distancecc[NV]) {
distancecc[NV]=d;
pred[NV]=U;
}
}

}

return pred;

}


==========================================================
public class ExtraireMin {

public static int ExtraireMin(int [] distancecc, boolean [] marque){
int x =Integer.MAX_VALUE;
int y=0;

for (int i = 0; i < distancecc.length; i++) {
if (!marque[i] && distancecc[i]< x) {

y=i;
x=distancecc[i];

}

}

return y;
}
}