Dijkstra K plus court chemin algorithme en Java - Tutorial

Version imprimable

12/08/2014, 19h08
geforce

Dijkstra K plus court chemin algorithme en Java - Tutorial

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 !!)
12/08/2014, 22h42
geforce

1 pièce(s) jointe(s)

//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.
15/08/2014, 04h12
geforce

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

Merci
15/08/2014, 20h27
ToTo13

Citation:

Envoyé par geforce

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.
17/08/2014, 06h03
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.
17/08/2014, 10h39
ToTo13

euh... :koi:
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.
17/08/2014, 15h06
voblivion

2 pièce(s) jointe(s)

Hmm .. ça me rappelle quelques cours de cette année. Je ne sais pas si c'est exactement ton problème mais ..

Tu regardes les sommets atteignable après un tour. Tu associe à ces sommets la valeur du trajet.
Tu regardes les sommets atteignable après deux tours (= après un tour en partant de ceux atteignable après un tour(donc plus depuis la source)). Tu associe à ces sommets la valeur du trajet si ils n'en ont pas déjà, et celle du plus court si un trajet les atteignait déjà.
Tu regardes les sommets atteignable après trois tours (= après un tour en partant de ceux atteignable après deux tour(donc par exemple pasdepuis ceux pour lesquels le trajet après deux coups est plus long que celui après un coup)). Tu associe à ces sommets la valeur du trajet si ils n'en ont pas déjà, et celle du plus court si un trajet les atteignait déjà.
Etc.

Après je ne sais plus quand il faut s'arrêter, mais en y réfléchissant...

Edit : Je vais préciser l'algorithme auquel je pense :
Explication écrite :
C'est un algorithme récursif au cours duquel chaque sommet possède soit le booléen "FALSE" soit une valeur "v" où la "valeur" est la taille du chemin pour l'atteindr. Il y a aussi une liste L qui contient la liste des "sources" à un moment donné de l'algorithme.
Initialement, le sommet A possède la valeur 0 et les autres sommets possèdent la valeur "FALSE". La liste L est le singleton {A}.
À chaque tour on définit M la liste des sommets atteignables en un tour depuis ceux dans L. Pour chacun des sommets de M, on calcul la valeur associé v' (ex: on atteint le sommet C depuis le sommet B de valeur 4 par un chemin de valeur 3 : la valeur associée est alors 4 + 3 = 7). Pour un sommet "m" de M, si il avait la valeur "FALSE" on lui donne à présent la valeur calculée v'. Si "m" avait déjà une valeur v, on la compare à celle calculée comme suit : si v' < v, "m" prend désormais la valeur v'; sinon, "m" garde la valeur v ET SORT DE LA LISTE M. Enfin pour le tour d'après on pose L = M. On continue tant que L n'est pas vide. Dès que c'est le cas, on s'arrête et la valeur du sommet de sortie Z est celle du plus court chemin.
On peut aussi garder une trace du chemin en enregistrant avec chaque sommet, plutôt que la valeur, le couple (valeur, chemin).
NB : pas la peine de regarder en combien de tour on arrive à tel ou tel sommet.

Petite explication imagée : les cercles rouges sont ceux de L, ceux oranges sont ceux de M, les valeurs rouges sont celles des sommets du tour précédents et celles oranges sont celles calculées lors du tour courant. On barre en vert à la fin de chaque tour la valeur inadéquate, et si c'était celle orange le sommet ne devient pas rouge au tour suivant :
Pièce jointe 153957
Pièce jointe 153958

Edit-Remarque :
Une variante destinée aux graphs (non obligatoirement finis ou) très grands, mais dont les chemins ne peuvent avoir que des valeurs strictement positive, consiste à sortir de la liste L tout sommet de valeur supérieure à celle de Z une fois que le sommet Z possède une valeur (même non définitive).
21/08/2014, 18h41
geforce

Citation:

Envoyé par ToTo13

:koi:
Il suffit de faire la même chose en partant des autres sommets.

Oui c'est bien ça, mais ce n’est pas aussi simple.
une réflexion : je me dis supposant qu'il suffit de bouclé sur le même algorithme qui me trouve 1 seul chemin (le plus cours) et je ne veux pas retombé sur ce même chemin et j'ajoute le critère de couverture à 100% des Nœuds et Arêtes.

- il faut une façon qui permet de déprécié les chemins déjà utilisés sans les annules (ça reste des possibilités) pour trouver un chemin le plus cours, mais qui soit plus longue que le 1er sinon y un problème dans l'algorithme et la même chose pour les tours suivants ..... (il faut plus d'information pour l'implémenté en jAVA)

Je cherche y t'il un nom pour ce type d'algorithme (je suppose qu'il existe, mais je trouve pas) ?
21/08/2014, 18h43
geforce

Citation:

Envoyé par voblivion

Hmm .. ça me rappelle quelques cours de cette année. Je ne sais pas si c'est exactement ton problème mais ..

J'ai suivis tes instruction je compris mais pas tout, y t'il un nom de cette algo ? (pour faire plus d'investigation il ce peu qu'il fasse mon affaire)
Merci