Chemin le plus court et graphe

[invite9a93ada1]

Bonjour à toutes et à tous !

Je suis en train de travailler sur l'algorithme de plus court chemin (un noeud vers tous les autres noeuds) dans le cas des graphes (aussi connu sous le nom : "Algorithme de Dijkstra").

J'ai déjà cherché les pseudo code et essayer de comprendre comment cet algorithme fonctionne.
Mon problème se situe au niveau de l'implémentation en Java.
Le chemin obtenu à l'exécution n'est pas le bon, ce qui me frustre beaucoup car je n'arrive pas à le corriger.
Pouvez vous m'aider ?

Globalement, j'ai deux vecteurs, Initial qui contient l'ensemble des noeuds de mon graphe et Solution qui contient les noeuds dans l'ordre du parcours le plus court. Donc au fur et à mesure, je parcours, je supprime les noeuds plus cours et l'ajoute dans le vecteur solution. Quand le vecteur Initialest vide, cela sera fini et j'aurais parcouru en entier le graphe.
J'ai commenté mon code et mis des variables au nom explicite pour une meilleur compréhension (pièce jointe)


J'utilise 4 classes:
* graphe (construit le graphe et implement dijkstra)
* Liste (Liste d'adjacence)
* noeud (créer un noeud)
* test



Voici un exemple de Graphe graphe.jpg

J'ai implémenté ce graphe directement dans mon programme (vous n'avez donc qu'à exécuter).

J'obtiens en résultat :
A partir du noeuds S0, la plus petite distance pour aller au noeuds
0 est 0
1 est 11
2 est 18
3 est 11
4 est 18
5 est 9999 (Infini)

Logiquement, j'aurais du obtenir :
A partir du noeuds S0, la plus petite distance pour aller au noeuds
0 est 0
1 est 2
2 est 5 (par S1 et S4)
3 est 7 (par S1 et S4)
4 est 3
5 est 9999 (Infini)

Je vous remercie d'avance pour votre aide
-----

[JPL]

Pour la commodité de la consultation met tes programmes en utilisant la balise Code (# dans la barre d'outils). Merci.

[invite9a93ada1]

Bonjour,

En fait, je les avais mis en pièce jointe pour éviter de faire un message trop long.
Mais je les mets avec la balise Code si vous voulez.


*Classe graph :

import java.util.Vector;

public class graph {
	
	public Liste adjacence[]; 

	 
	graph(int nb_sommets, int nb_arcs){ 
		adjacence = new Liste[nb_sommets]; 
		for (int i = 0; i < nb_sommets; i++) 
			adjacence[i] = null; 
	} 

	
	
	public void afficher() {  //pour afficher le graphe
		
		for (int i = 0; i < adjacence.length; i++){ 
			System.out.print("sommet "+i+" : "); 
			if (adjacence[i]!=null) { 
				Liste tmp2 = adjacence[i]; 
				while(tmp2!=null) { 
					System.out.print(tmp2.num_noeud + " " + tmp2.valeur + " ");
					if (tmp2.suivant != null) 
						System.out.print(tmp2.suivant.num_noeud + " -> "); 
					tmp2 = tmp2.suivant; 
				} 
			}
			System.out.println(" null");
		}
	}

		
	public boolean arc (int source, int dest){ 	//vérifie s'il y a un arc entre deux noeuds
		boolean Existe=false; 
		Liste temporary=adjacence[source];
		
		while(temporary!=null){
			if(temporary.num_noeud==dest){
				Existe=true; 
			}	
			temporary=temporary.suivant;
		}
		
		return Existe; 
	} 

	
	public int v_arc(int source, int dest){ //retourne la valeur de l'arc entre les deux noeuds
		int Val = 999999;
		if(arc(source, dest)){
			Val=adjacence[source].valeur;
		}
		
		
		
		return Val; 
	} 
	

public Vector dijkstra(int num_sommet){ 
		
		final int INF = 99999; 		//Inf correspond à l'Infini, c'est à dire qu'il n'y a pas d'arc entre les deux noeuds considérés
		
		Vector Solution = new Vector(); //vector Solution qui contient le plus petit parcours selon dijkstra 
		Vector Initial = new Vector(); //vector Initial qui contient l'ensemble des noeuds
		
		//L'objectif est de considérer le noeuds le plus court par rapport au noeud courant, l'ajouter à Solution et le supprimer au Vector Initial au fur et à mesure
		//Lorsque le vecteur Initial est vide, on aura parcourus l'ensemble du graphe
		
		
		for (int i = 0; i < adjacence.length; i++){ // étape 1 : phase d'initialisation selon Dijkstra à l'infini
			if (i!=num_sommet) Initial.addElement(new noeud(i,INF)); 
			else Initial.addElement(new noeud(i,0)); 
		} 
		System.out.println("S:"); 
		for (int i = 0; i < Solution.size(); i++){ //affiche le vecteur Solution
			System.out.println(((noeud)Solution.elementAt(i)).sommet+", "+((noeud)Solution.elementAt(i)).distance); 
		} 
	
		
			int poids=INF; //initialisation
			int indice=0;
			Liste tmpp=adjacence[num_sommet];
			
			//étape 2 : parcours pour trouver le noeud avec la plus petite distance du noeud courant
			
		while(!Initial.isEmpty()){
			while(tmpp!=null){
				if (poids>tmpp.valeur){
					poids=tmpp.valeur;
					indice=num_sommet;
					}
				tmpp=tmpp.suivant; 
			  }
			
				poids=INF;//on remet poids= INF pour la prochaine boucle
				
					int dn = ((noeud) Initial.elementAt(indice)).distance; //on reconstitue le noeud avec la plus petite distance
					int sn = ((noeud)Initial.elementAt(indice)).sommet;
					noeud n=new noeud (sn,dn); 
					Solution.addElement(n); // ajout
					Initial.removeElementAt(indice);  //supprime
					
					for (int i = 0; i < Initial.size(); i++){  //Parcourir Initial et on vérifie si le chemin est effecivement le plus court
						noeud y=new noeud(((noeud)Initial.elementAt(i)).sommet,((noeud)Initial.elementAt(i)).distance);
						if  (arc(n. sommet ,y. sommet )) { 
							int  d=n. distance +v_arc(n. sommet ,y. sommet ); 
							if  (d<y. distance ) { 
							y. distance =d; 
							Initial.setElementAt(y,i);                          //met à jour les distance
							
							}
						}
					}
		}
		
	return Solution;// on retourne solution
	
	}

public void parcours(){ //construction du graphe
	
	adjacence[0]= new Liste(new Integer(1), adjacence[0],new Integer(2)); 
	adjacence[0]= new Liste(new Integer(3), adjacence[0],new Integer(11)); 
	adjacence[1]= new Liste(new Integer(2), adjacence[1],new Integer(4)); 
	adjacence[1]= new Liste(new Integer(4), adjacence[1],new Integer(1)); 
	adjacence[1]= new Liste(new Integer(3), adjacence[1],new Integer(7)); 
	adjacence[4]= new Liste(new Integer(3), adjacence[4],new Integer(4)); 
	adjacence[4]= new Liste(new Integer(2), adjacence[4],new Integer(2)); 
	adjacence[5]= new Liste(new Integer(3), adjacence[5],new Integer(1)); 
	this.afficher();
	
	 
} 




}

*Classe Liste

public class Liste {
	int num_noeud; 
	int valeur; 
	
	// On utilise les Listes d'adjacences et elles vont indiquer vers quels noeuds pointent le noeud courant 

	Liste suivant; 
	Liste (int n, Liste t, int v) { 
		num_noeud=n;
		valeur=v;
		suivant=t;
	}
	@Override
	public String toString() {
		return "S" + num_noeud + ", suivant=" + suivant
				+ " valeur=" + valeur + "]";
	}
	

}

* Classe noeud

public class noeud {
	int sommet; 
	int distance; 
	noeud(int s, int d){ 
		sommet=s;
		distance=d;
	}
	@Override
	public String toString() {
		return "Element [distance=" + distance + ", S" + sommet + "]";
	}
	
}

*Classe test

import java.util.Vector;


public class test {
	public static void main(String[] args) {
		
		graph h = new graph(6, 8);
		h.parcours();                 //ici j'initialise mon graphe au préalable avec les sommets et distances initiales
		
		Vector Solution=h.dijkstra(0);	//au calcul le plus cours chemin à partir du sommet 0;
		 for (int i = 0; i < Solution.size(); i++) {
		 System.out.println(((noeud) Solution.elementAt(i)).sommet + ", " + ((noeud) Solution.elementAt(i)).distance);
		  }
		
	}
}

Merci de votre aide

[invite9a93ada1]

Personne, si vous avez des questions, je peux essayer de reformuler ?

Merci

[A voir en vidéo sur Futura]