Version imprimable
Bonjour a tous,
Est ce que l'un d'entre vous pour m'expliquer comment fonctionne l'algo de Dijkstra ?
J'ai lu le contenu de plusieurs sites et de plusieurs post et je ne comprend pas grand chose.
J'aimerais savoir ce que represente la matrice au départ et comment elle est traité dans les calcul de chemin ?
Merci d'avance.
S'il vous plait un petit coup de main, je demande juste une petite explication, ou si vous connaissez un site qui explique de facon precise, clair et simple.
Merci de m'aider.
Bonjour,
une petite recherche sur google:
http://wims.unice.fr/wims/fr_U1~graph~dijkstra.fr.html
http://forumsig.symen.ch/showthread.php?t=1394
bonjour,
J'avais deja visité ces 2 sites.
http://wims.unice.fr/wims/fr_U1~graph~dijkstra.fr.html
ne m'aide pas a comprendre la logique de l'algorithme, j'arrive a faire l'exo proposé sur le site mais comprendre l'algo a partir de cet exo est autre chose.
http://www.apprendre-en-ligne.net/graphes/
pour ce site c'est encore pire je ne comprend pas un mot a ces histoire de vecteur et donc encore moins comment le mettre en pratique dans mon programme.
Hum, j'ai vu ca en cours mais là, de tete, je ne pourrais pas vraiment t'aider.
Je chercherais dans mes cours mais je te garanti rien car j'ai déménager depuis et c'est possible qu'ils soient dans un coin sombre quelque part ...
La matrice de départ, la matrice des coûts, représente le coût pour aller d'un point à un autre. La diagonale est toujours nulle puisque le coût pour aller de i à i est 0. Dans les autres cases, tu donnes le cout pour aller du point i aux points adjacents de i (c'est la valeur des arcs (i, points adjacents de i). Comme au départ, tu ne connais pas le cout pour aller du point i à tous les autres points, certaines cases ont pour valeur infini.
Autrement dans l'algorithme, on fait évoluer au fur et à mesure cette matrice, on réévalue les coûts entre les différents points, au fur et à mesure qu'on trouve des chemins plus courts pour aller d'un point à un autre.