Discussion :

[geforce]

Bonjour à tous,
J'ai suivi le Tutorial suivant pour mon apprentissage a l'algorithme, mais a l'exécution il me donnée les valeurs suivantes :
http://www.vogella.com/tutorials/Jav...a/article.html
-------------------------------------------------------
T E S T S
-------------------------------------------------------
Running com.dijkstra.DijkstraAlgorithmNGTest
Node_0
Node_2
Node_7
Node_9
Node_10

Ce qui devrait représenter le plus court chemin dans le graphe suivant:
("Edge_0", 0, 1, 85);
("Edge_1", 0, 2, 217);
("Edge_2", 0, 4, 173);
("Edge_3", 2, 6, 186);
("Edge_4", 2, 7, 103);
("Edge_5", 3, 7, 183);
("Edge_6", 5, 8, 250);
("Edge_7", 8, 9, 84);
("Edge_8", 7, 9, 167);
("Edge_9", 4, 9, 502);
("Edge_10", 9, 10, 40);
("Edge_11", 1, 10, 600);

J'ai donc décidé le graphe sur papier pour faire une représentation avec le résultat : Node_0, Node_2, Node_7, Node_9, Node_10.

Mais je vois ça n’a pas de sens qu'il y une erreur quelque part ? (Mais quoi ? Merci de m'aider !!)

[geforce]

//A, B, C, D, E = 0, 1, 2, 3, 4
addLane("Edge_0", 0, 1, 2);
addLane("Edge_1", 0, 2, 6);
addLane("Edge_2", 1, 4, 2);
addLane("Edge_3", 2, 1, 3);
addLane("Edge_4", 2, 3, 2);
addLane("Edge_5", 3, 3, 0);
addLane("Edge_6", 4, 3, 7);
addLane("Edge_7", 4, 2, 1);

J'ai une erreur de l'algorithme que j'ai fait cette tentative de représentation du graphe suivant.

[geforce]

Comment en peu reconstitué le vrais Graphe à partir des lignes initialisation du test ?

Merci

[ToTo13]

Comment en peu reconstitué le vrais Graphe à partir des lignes initialisation du test ?

Le but de cet algo est de donner le plus court chemin dans un graphe à partir d'un point source. Le temps/distance entre deux sommets est donné par les valeurs/poids des arrêtes.
Donc dans ton cas, tu aurais :
- B = 2
- E = 4
- C = 5 (c'est mon couteux de passer par B et E, que d'aller directement depuis la source).
- D = 7.

[geforce]

Oui je te remercie ToTo13.
j'ai aussi des difficultés a comprendre de concepts des K plus cours chemins ? B = 2, E = 4, C = 5, D = 7 est la plus optimale, mais ne couvre pas tout les arêtes. Si on ajouter le critère de couverture 100% des arête !!
Comment calculé les autres chemins ??

Ma référence :
Dans les principe de l'algorithme de Dijkstra (sur la théorie des graphes) il est dit que « l'idée de l'algorithme de Dijkstra est de calculer de proche en proche, l'arborescence de plus courtes distances, issu du sommet S à un sommet donné P »
Et que le « Plus court chemin pour tous couples de sommets. L'idée est ici d'obtenir le même résultat que précédemment, mais pour l'ensemble des couples du graphe. Ou aussi être amené à calculer les plus courts chemins à destination uniques, mais il s'agit en fait du même problème. »


Merci.

[ToTo13]

euh...
Il suffit de faire la même chose en partant des autres sommets.
Ou je ne comprends pas bien ce que tu veux dire/faire.