Graphe pondéré : Algorithme de Dijkstra

On va voir une variante, plus complexe, de l’algorithme BFS : l’algorithme de Dijkstra. Cet algorithme permettra de calculer toutes les distances entre un sommet de départ r et les autres sommets, mais cette fois ci, ce graphe est pondéré.

Pour un graphe pondéré, chaque arête (u,v) a une longueur notée l(u,v). Pour certaines applications, on parle plutôt de poids d’une arête. Jusqu’à présent nous n’avons traité que le cas particulier où l(u,v) = 1.

Comme l’algorithme précédent, celui-ci donnera la distance selon le plus court chemin.

Au départ, aucune distance n’est connue. Les distances provisoires notées distG(r,u), sont mises à l’infini : pour tout u, distG(r,u) = ∞

Le graphe suivant servira d’exemple :

graphe exemple Dijkstra — exemple de graphe pondéré

Les longueurs des arêtes sur le schéma ne sont pas proportionnelles à leur poids.

La méthode employée diffère légèrement de celle du parcours en largeur. Il faudra également utiliser une liste L de sommet à parcourir. Mais cette liste est constament remise à jour (triée) en fonction des longueurs des arêtes constatées, comme on le verra plus loin.

De plus, il faudra mémoriser le sommet parent d’un sommet visité. Ce sommet parent pourra être modifié si on trouve un chemin plus court pour atteindre ce sommet depuis le sommet de départ.

algorithme

On part du sommet r :

On visite tous les noeuds fils de r. Pour chaque sommet adjacent u: On note la distance qui sépare r de u selon la longueur de l’arête. Et on note le sommet parent. On ajoute chaque sommet dans la liste L.
On trie la liste L par ordre de distance à rcroissante.
On colore en rouge le sommet r lorsque tous les sommets adjacents ont été visités. Et on retire r de la liste.
On passe au sommet v pour poursuivre l’exploration : le premier à gauche dans la liste (celui le plus proche de r).
On visite tous les sommets voisins de v. On les ajoute dans la liste L.
Pour chaque voisin w du sommet v : si distG(r,w) < distG(r,v) + distG(v,w), c’est que le sommet w a déjà été visité, et que le chemin déjà trouvé est plus court que le chemin actuel. On ne fait rien.
si distG(r,w) > distG(r,v) + distG(v,w), c’est que le sommet w a peut être été visité, mais que le chemin actuel est le plus court. On note alors la nouvelle valeur de la distance : distG(r,w) = distG(r,v) + distG(v,w). Et on note que le parent du sommet w est v. C’est actuellement le meilleur chemin.
Puis, lorsque tous les voisins de v ont été visités, on revient au point 2 pour v (trier la liste L, coloration en rouge,…).

Ce qui change par rapport à l’algorithme précédent, c’est surtout le nouveau choix de sommet à visiter lors du parcours du graphe : lorsque tous les noeuds fils d’un sommet ont été visités, et que l’on a mémorisé leur distance au sommet de départ, on choisi d’explorer le sommet le plus proche, celui le plus à gauche dans la liste L.

Il faut donc trier cette liste à la fin de chaque exploration.

Illustration

On démarre du sommet Bvoisins. Après le parcours de ses voisins, la liste L contient les sommets D,E,F classés par ordre de distance croissante :

$$L = [(D,2), (E,5), (F,10)]$$

D est à une distance de 2
E est à une distance de 5
F est à une distance de 10

parcours initial Dijkstra — L = [(D,2), (E,5), (F,10)]

On tient à jour le tableau des distances au sommet de départ, B:

exploration depuis le sommet…	A	C	D	E	F	G	H
B	∞	∞	2	5	10	∞	∞

Ensuite, on passe au sommet D, le plus proche de B (le plus à gauche dans la liste) :

C est à une distance 2+3 = 5 de B
H est à une distance 2+4 = 6 de B
A est à une distance 2+9 = 11 de B

On ajoute C, H et A à la liste. L = [(E,5), (F,10), (C,5), (H,6), (A,11)]

Puis on trie cette liste:

parcours 2 Dijkstra — L = [(C,5), (E,5), (H,6), (F,10), (A,11)]

On met à jour les distance des sommets voisins :

exploration depuis le sommet…	A	C	D	E	F	G	H
D	11	5				∞	6

Les valeurs pour D, E et F ne sont pas remises à jour. On ne les mentionne pas dans ce tableau.

Le sommet suivant à traiter est alors le C. Ses voisins sont E, et G. L’examen du chemin vers E ne change rien : le chemin B,D,C,E a une longueur plus importante que le chemin direct B,E (12>5). Par contre, le chemin vers G offre une nouvelle distance :

G est à une distance 5+2 = 7 de B :

exploration depuis le sommet…	A	C	D	E	F	G	H
C						7

On ajoute G à la liste et on trie:

parcours 3 Dijkstra — L = [(E,5), (H,6), (G,7), (F,10), (A,11)]

On passe au sommet E : il n’y a pas de modification de la distance de B à C en passant par E. Comme C est le seul fils, on retire E de la liste L et on passe au sommet suivant, le H. Alors :

A est à une distance 6+1 = 7 du noeud B. C’est le meilleur chemin.
G est à une distance 6+2 = 8 du noeud B en passant par H. Cette valeur n’est pas enregistrée car il existe un chemin plus court.