Discussion :

[Jeff_as_jefferson]

Bonjour,

J'ai un problème avec Dijkstra (calculer le plus court chemin sur un réseau de transport). Ça fait 2 jours que j'essaie de l'implanter mais ça ne marche jamais.

Ici j'écris :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
		for(Station st : reseau){
			pasVu.add(st);
		}
		for(Station st : pasVu){
			System.out.println("   ->€ "+st.getNom());
		}

Le programme m'écrit bien en partie :

->€ Barbès - Rochechouart
->€ Gare du Nord
->€ Château d'Eau

Mais après un peu plus loin dans la fonction j'écris :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
	for(Station st2 : voisins){
		System.out.println("  ? "+st2.getNom());
		if(pasVu.contains(st2)){
			//st2.distParcouru=st.getMinPoids(st2);
			//pasVu.remove(st2);
			//vu.add(st2);
			System.out.println("     -> "+st2.getNom());
		}

et il me répond :

Château d'Eau ## encore 87
? Gare du Nord
? Gare de l'Est (Verdun)
-> Gare de l'Est (Verdun)

Pour moi ça signifie qu'il ne rentre pas dans la condition if

st2 décrit toutes les stations liées aux stations déjà vues du réseau. Je suis sur que le réseau comprend bien la station :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
	for(Station st : reseau){
		if(pasVu.contains(st)){
			System.out.println(st.getNom()+" est dans pasVu");
		}
	}

répond

Barbès - Rochechouart est dans pasVu
Gare du Nord est dans pasVu
Château d'Eau est dans pasVu

Pour mettre les stations dans le tableau "voisins" je ne crois pas avoir de problèmes de référence :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
		for(Station st2 : st.getPrec()){
			voisins.add(st2);
		}
		for(Station st2 : st.getSucc()){
			voisins.add(st2);
		}

Et lorsque je désigne les précédents/successeurs de chaque ligne ça me semble bien être la même référence que lorsque j'ajoute dans le tableau réseau :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
		tmp = new Station(ligne, ligneRATP);
			reseau.add(tmp);
			if(i!=0){
				tmpOLD.addSucc(tmp, poidsOLD);
				tmp.addPrec(tmpOLD, poidsOLD);

Je ne comprends pas pourquoi la première fois il me dit que Gare du Nord est dans la liste pasVu et pas la deuxième fois.

Quelqu'un connait un bug de ce genre ? Avez vous besoin de plus d'infos ? Sauriez-vous m'aider ?

Je comprends toujours pas mais ce que vous m'avez dit de faire fonctionne. merci

[the-gtm]

La méthode contains des collections se base sur le test equals(...) des objets contenus. A priori je dirais que tu n'a pas implémenté cette méthode dans ta classe Station. Quand equals n'est pas implémentée, c'est l'implémentation de la classe Object qui est appelée, celle ci renvoie true si le test == est vrai.

Au passage quand tu surcharge equals, il est recommandé de surcharger hashcode aussi

[sinok]

Le pourquoi et le comment se trouvant dans la FAQ:
http://java.developpez.com/faq/java/...#DIVERS_equals
http://java.developpez.com/faq/java/...IVERS_hashCode