Embedded Files
L'algorithme dû à Dijkstra est basé sur le principe suivant :
Si le plus court chemin reliant le sommet de départ s0s0 à un autre sommet S passe par les sommets s1s1, s2s2, …, sksk alors, les différentes étapes sont aussi les plus courts chemins reliant A aux différents sommets s1s1, s2s2, …, sksk.
On construit de proche en proche le chemin cherché en choisissant à chaque itération de l'algorithme, un sommet sisi du graphe parmi ceux qui n'ont pas encore été traités, tel que la longueur connue provisoirement du plus court chemin allant de s0s0 à sisi soit la plus courte possible.
Page updated
Google Sites
Report abuse