Recherche du plus court chemin

La méthode est expliquée de deux façons.
Directement sur le graphe (si ce graphe est suffisamment simple) ou par construction d’un tableau (dès que le chemin devient un peu long).

► Algorithme de Dijkstra directement sur le graphe

Graphe 5	Pour le graphe ci-contre recherche du plus court chemin depuis A jusqu’à D. On écrira 0 en A (aller de A en A sans se déplacer). Puis (schéma suivant), deux possibilités : - soit aller en B, - soit aller en E. On ignore les autres points.
Graphe 6	On arrive en B depuis A en avançant de 4. En B on écrit (4A). On arrive en E depuis A en avançant de 2. En E on écrit (2A). Les possibilités de déplacement depuis A sont épuisées.
Graphe 7	On s’occupe des points où l’on est arrivé : - depuis B, on peut aller en E (ce qui ferait 5 donc plus que directement depuis A ce qui ne présente aucun intérêt), en C ou en D. - depuis E, on peut aller en B, ce qui diminue le parcours A-B. On barre la valeur précédente que l’on remplace par (3E). On peut aussi aller en C ou en D. On marque chacune des valeurs (voir schéma) en additionnant la longueur de l’arête parcourue et la valeur obtenue précédemment, on barre éventuellement celles qui seraient plus grandes.
Graphe 8	Il ne reste plus que de C à D, on constate que la longueur totale de ce chemin est plus courte que celles déjà obtenues que l’on barre. On peut alors dire que le chemin le plus court a une longueur de 7, que pour arriver en D il faut venir de C, depuis B, en venant de E depuis A. Le meilleur parcours est donc A - E - B - C - D.

► Algorithme de Dijkstra dans un tableau

Avec le même graphe, recherchons le plus court chemin depuis A jusqu’à D.

• Dans un tableau, placer en ligne les sommets par ordre alphabétique, le premier sommet étant le point de départ, le dernier le point d’arrivée (ce qui peut ne pas respecter l’ordre alphabétique pour ces deux là).


• Ligne n°1, dans la colonne A écrire 0 car c’est la distance lorsque l'on va de A à A sans se déplacer.
On écrit ∞ dans chacune des autres colonnes de cette ligne car pour aller de A à A sans se déplacer on donne une distance infinie aux autres points.
En fin de tableau, dans la colonne résultats, on écrit A car c’est le point qui permet d’avoir la meilleure distance depuis A.
A ne sera plus utilisé, on raye toute sa colonne (voir tableau).

• Ligne n°2 : on écrit les deux distances des points joignables depuis A.
Depuis A, on ne peut atteindre les autres points, on les affecte d’une distance ∞.
Depuis A, la plus courte distance de parcours est E que l’on écrit dans la colonne des résultats.

• Ligne n°3 : on raye les colonnes qui ne seront plus utilisées, on reporte les nouveaux calculs de distance (depuis les points B ou E).
On raye (ou on ne garde pas) les distances plus grandes.
On reporte B meilleur point, car sa distance depuis A est la plus courte.

• Ligne n°4 : depuis B et sa meilleure longueur (depuis A), on atteint C avec la meilleure distance.

• Ligne n°5 : depuis C, la longueur obtenue vers D, le point d’arrivée, est meilleure que celles obtenues depuis B ou E.
Alors le chemin le plus court a une longueur de 7, pour arriver en D : il faut venir de C, depuis B, en venant de E depuis A.

Le meilleur parcours est donc A - E - B - C - D.