Bonjour tout le monde !

Voila, je suis en train d'étudier l'algo de dijkstra cependant il y a une chose que je n'arrive pas à comprendre, c'est comment retrouver le plus court chemin une fois qu'on a rempli la matrice avec les étapes (celles où on remplit au fur et à mesure, la deuxième).

C'est ici que je m'inspire :
http://fr.wikipedia.org/wrg/wiki/Algorithme_de_Dijkstra

Parce que j'arrive à savoir si j'ai leur matrice toute remplie pour savoir le plus court chemin entre A et J ( J(487H) donc J vient de H, H(320C) donc H vient de C...etc)
et au final on a bien le plus court chemin J-H-C-A.

Cependant je ne vois pas comment ils remplissent la deuxième lettre dans la première colonne (celle où on a A, B(85A), F(165B),E(173A)..etc)

J'ai compris pour la première lettre, c'est quand le poids est fixé(c'est à dire souligné, à la prochaine ligne, on met cette lettre en premier, la distance j'ai compris aussi, mais la deuxième lettre je n'arrive pas à comprendre comment l'obtenir... Or c'est celle qui permet de savoir le plus court chemin. (et j'ai tout compris sauf ça... je sais construire le tableau..etc )

Merci d'avance pour l'aide et au revoir ^^

La deuxième lettre correspond au sommet d'où on est arrivé pour réaliser cette distance. Je vais t'expliquer sur l'exemple précédent avec les graphes, j'aime pas trop leur présentation sous forme de matrice c'est pas très intuitif comme façon de faire à mon avis.

http://fr.wikipedia.org/wiki/Algorithme_de_Dijkstra#Distance_entre_la_ville_A_et_la_ville_J

Regarde les étapes 4, 6 et 8.
A l'étape 4, en explorant le sommet "E", on trouve un chemin menant à la ville J, de longueur 675. On va alors stocker également le prédécesseur de J, qui correspond au sommet d'où on est arrivé. Là, on va donc stocker pred(J) = E.
A l'étape 6, on trouve un nouveau chemin qui arrive en J. Celui-ci provient de la ville H, et a une longueur de 487. Comme c'est mieux que le 675 précédent, on va mettre à jour la distance du noeud J, mais aussi son précécesseur : pred(J) = H.
A l'étape 8, on trouve un troisième chemin arrivant en J, celui-ci passe par I mais comme il n'améliore pas la distance, on garde pred(J) = H.

A la fin de l'algo, on retrouve le chemin en remontant les prédecesseurs.

de facon general, tu peux savoir si une arete est sur l'arbre des plus court chemin en verifiant si PCC(B) = PCC(A)+dist(A,B)

Ok je vois merci ^^ . C'est bon parfait.