Parcourir un graphe, c’est explorer ses sommets atteignables à partir d’un sommet de départ par un chemin ou par une chaîne. L’algorithme de Dijkstra permet de trouver les plus courts chemins.
I. Parcours en largeur et en profondeur
On part d’un sommet du graphe, déterminé à l’avance, puis on explore les sommets atteignables depuis celui-ci en respectant un ordre de traitement des sommets imposés par le type de parcours qu’on effectue. Éventuellement, cette procédure peut être réitérée depuis un autre sommet.
Considérons, par exemple, le graphe ci-contre orienté et prenons A comme sommet de départ. Par convention, on explore les voisins dans l’ordre alphabétique.
Deux stratégies de parcours sont envisageables :
le parcours en largeur (BFS en anglais pour breadth first search) où on explore en priorité tous les voisins de A puis tous les voisins des voisins de A, etc. Cela donne ici le parcours ABCDEFGH ;
le parcours en profondeur (DFS en anglais pour depth first search) où on explore en priorité les voisins du premier voisin de A puis récursivement ses voisins respectifs. Cela donne ici le parcours ABDGHEFC.
II. Algorithme de Dijkstra
On considère un graphe non orienté pondéré avec des poids positifs. L’algorithme de Dijkstra permet de trouver à partir d’un sommet i de départ fixé à l’avance les plus courts chemins menant à tout sommet accessible depuis i.
1) Fonctionnement de l’algorithme
On construit et on initialise trois listes :
la liste des sommets déjà explorés lst_e = [] ;
la liste des sommets atteignables par une arête depuis un sommet déjà exploré et qui n’ont pas encore été explorés : lst_v = [i] ;
la liste des distances à i et des pères (sommets permettant d’accéder de manière optimale au sommet cible) lst_d. Initialement, lst_d est composée de n fois [float.inf, None] sauf lst_d[i] = [0, None]. La valeur float.inf est utilisée pour dénoter un sommet qui n’est pas encore accessible, elle est plus grande que tout nombre, permettant des comparaisons aisées.
Tant que lst_v n’est pas vide, on sélectionne le sommet s de lst_v qui a la plus courte distance à i parmi les sommets de lst_v. On supprime ce sommet de lst_v et on l’ajoute à lst_e.
Pour chaque voisin v de s on regarde s’il est dans lst_e. Si ce n’est pas le cas, on l’y ajoute et on met à jour lst_d :
S’il est présent dans lst_e, on regarde si lst_d[s][0] + distance(s, v) est inférieur à lst_d[v][0] auquel cas on remet à jour de la même façon lst_d. Lorsque lst_v est vide l’algorithme s’arrête.
On connaît alors la plus courte distance de i à tout sommet accessible et, en remontant dans l’ordre les pères, on peut reconstituer le chemin qui a cette longueur.
2) Lecture du résultat sur un exemple
Le graphe suivant représente les distances entre plusieurs villes.
On applique l’algorithme (None est noté N et + ∞ est noté inf) :
Le plus court chemin de 0 à 6 s’obtient en « remontant » les sommets prédécesseurs depuis 6 : on arrive à 6 depuis 4 ; lui-même précédé de 3 ; lui-même précédé de 1 ; lui-même précédé de 0 : le chemin est donc 0-1-3-4-6.
À noter
L’algorithme de Dijkstra est notamment utilisé pour le routage sur internet.