Dijkstra's algorithm

Reading time20 min

En bref

Résumé de l’article

Dans cet article, vous apprendrez comment naviguer dans un graphe pondéré. Vous verrez que les parcours vus précédemment ne peuvent pas être utilisés directement. Nous introduisons donc un autre algorithme de parcours : l’algorithme de Dijkstra.

Points clés

  • L’algorithme de Dijkstra étend le BFS pour effectuer un parcours sur des graphes pondérés.

  • Il trouve le chemin le plus court entre des sommets dans des graphes à poids positifs.

  • En général, il a une complexité de $O(|E| + |V| \cdot log(|V|))$.

Contenu de l’article

1 — Vidéo

Veuillez regarder la vidéo ci-dessous. Vous pouvez également lire les transcriptions si vous préférez.

Information

Bonjour, et bienvenue dans cette leçon sur l’algorithme de Dijkstra ! Cette semaine, nous allons parler des plus courts chemins dans les graphes pondérés. Les algorithmes de parcours de graphe que nous avons déjà vus dans la leçon précédente ne peuvent pas être appliqués directement pour trouver les plus courts chemins dans les graphes pondérés.

Graphe pondéré

Pour illustrer pourquoi les algorithmes de parcours de graphe déjà présentés ne fonctionnent pas nécessairement pour les graphes pondérés, considérez le graphe jouet suivant.

Ici, une recherche en largeur, BFS, à partir du sommet $v_1$, ne produira pas un arbre couvrant des plus courts chemins. Par exemple, le plus court chemin réel de $v_1$ à $v_3$ est $(\{v_1,v_2\}, \{v_2,v_3\})$, alors que le chemin trouvé avec un BFS est $(\{v_1,v_3\})$.

C’est parce qu’un BFS privilégie un plus petit nombre de sauts depuis le sommet initial, indépendamment des poids.

Algorithme de Dijkstra

L’algorithme de Dijkstra est une modification du BFS qui nous permet de trouver les plus courts chemins, même en présence de poids, à condition que ceux-ci soient non négatifs.

Une petite remarque sur les poids. Jusqu'à présent dans ce MOOC, nous n'avons considéré que des poids non négatifs. Dans certains cas, il pourrait être pertinent d'ajouter des poids négatifs.

Par exemple, imaginez un chauffeur de taxi qui peut voyager entre des villes. Parfois il gagne de l'argent car il a un client et parfois il perd de l'argent car il voyage seul. On pourrait donc considérer un graphe dont les sommets représentent les villes et les arêtes sont pondérées par le coût du voyage correspondant. Certains poids seraient alors positifs et d'autres négatifs.

Revenons aux graphes avec des poids non négatifs. La façon la plus simple de décrire l’algorithme de Dijkstra est d’imaginer le sommet de départ comme un robinet d’où coule de l’eau. L’eau progressera le long des sommets et traversera le graphe à une vitesse inversement proportionnelle aux poids des arêtes, donc elle atteindra d’abord les sommets les plus proches.

En d’autres termes, l’algorithme de Dijkstra est un algorithme de parcours dans lequel les sommets sont visités par ordre croissant de distance depuis le sommet initial.

À chaque étape, l'algorithme de Dijkstra stocke deux types d'informations : 1) quels sommets ont déjà été explorés ; et 2) une approximation des distances de $v_1$ à tous les autres sommets du graphe.

L'algorithme de Dijkstra répète deux étapes. À l'étape 1, il sélectionne un sommet non exploré $v$ qui est à distance minimale de $v_1$. À l'étape 2, il met à jour les distances de $v_1$ aux autres sommets du graphe, en utilisant les informations sur $v$ et ses voisins.

Notez que l’algorithme donne toujours un arbre couvrant des chemins minimum dans le graphe, à condition que les poids soient non négatifs. Nous n’allons pas prouver ce résultat ici, mais ce n’est pas si difficile de faire un très bel exercice si vous souhaitez approfondir un peu plus les concepts décrits dans cette leçon.

Décrivons plus précisément comment fonctionne l'algorithme de Dijkstra à l'aide de l'exemple suivant. Nous allons construire un arbre couvrant minimum à partir du sommet $v_1$ dans ce graphe.

Nous initialisons donc deux structures de données : d'abord, l'ensemble des sommets explorés, qui est initialement vide, et ensuite, le tableau des distances de $v_1$ aux autres sommets du graphe, initialisé à $+\infty$ partout sauf pour $v_1$, où nous insérons un 0.

La première étape consiste à sélectionner un sommet non exploré qui est à distance minimale du sommet de départ. Ici, nous sélectionnons $v_1$ comme sommet de départ et l'ajoutons à l'ensemble des sommets explorés.

La deuxième étape consiste à mettre à jour les distances en tenant compte du sommet sélectionné $v_1$ et de ses voisins. Ici, $v_1$ a deux voisins : $v_2$ et $v_3$. Les atteindre en un saut depuis $v_1$ coûte respectivement 5 et 3. Nous mettons donc à jour nos distances depuis $v_1$ en disant que $v_2$ est à distance 5 et $v_3$ à distance 3. Notez que la longueur d'un plus court chemin de $v_1$ à $v_2$ est en réalité 4, mais nous ne pouvons pas encore le dire avec les résultats de l'algorithme seuls.

Commençons maintenant une nouvelle itération de l'algorithme. À la première étape, nous sélectionnons un sommet non exploré à distance minimale de $v_1$. Ici, nous choisissons $v_3$, qui est à distance 3. Nous l'ajoutons à l'ensemble des sommets explorés.

À la deuxième étape, nous regardons les voisins de $v_3$, qui sont $v_2$ et $v_7$, avec des poids correspondants de 1 et 2. Donc, si nous voulons atteindre $v_2$ en passant par $v_3$ un saut avant, nous avons un coût total de 3, qui est le coût pour aller à $v_3$, plus 1, qui est le coût d'un saut de $v_3$ à $v_2$. C'est mieux que la distance précédente estimée pour $v_2$, donc nous modifions les distances en conséquence. Quant à $v_7$, nous avons maintenant une distance estimée de 3, le coût d'aller à $v_3$ plus 2, qui est le coût d'un saut de $v_3$ à $v_7$.

Une nouvelle itération commence. Nous sélectionnons maintenant le prochain sommet non exploré avec la plus petite distance, qui est $v_2$. Nous l'ajoutons à l'ensemble des sommets explorés.

Le sommet $v_2$ a deux voisins, $v_4$ et $v_7$. Le sommet $v_4$ est estimé à une distance de $4 + 2 = 6$, et $v_7$ à une distance de $4 + 1 = 5$. Nous mettons donc à jour la distance vers $v_4$. Quant à $v_7$, la nouvelle distance trouvée n'est pas meilleure que l'ancienne, donc cela n'a pas d'effet.

Une nouvelle itération commence. Nous sélectionnons $v_7$ à distance 5 et l'ajoutons à la liste des sommets explorés. Et ainsi de suite...

Finalement, nous obtenons l'arbre couvrant suivant.

Mots de conclusion

C’est tout pour cette leçon ! Nous verrons ensuite comment implémenter l’algorithme de Dijkstra en utilisant des tas minimum.

Pour aller plus loin

2 — Propriétés de l’algorithme de Dijkstra

2.1 — Terminaison & correction

L’algorithme de Dijkstra se termine et est correct si tous les poids dans le graphe sont strictement positifs.

Preuve

La preuve de correction et de terminaison pour l’algorithme de Dijkstra est plus compliquée que celles que nous avons déjà vues pour des algorithmes de parcours plus simples. Nous allons faire les deux en même temps.

Terminaison

Supposons une file de priorité (ici, un tas minimum) pour laquelle toutes les opérations se terminent et sont correctes. Si la notion de tas minimum ne vous dit rien, vous devriez lire cet article d’abord.

Pour la preuve, nous procéderons par récurrence avec la propriété suivante : tous les sommets qui ont été retirés de la file de priorité sont tels que leurs distances depuis le sommet initial ont été calculées et enregistrées, et les sommets restants, s’il y en a, sont tous à une distance plus grande.

Nous remarquons trivialement que cette affirmation est vraie au premier passage dans la boucle, lorsque nous retirons le sommet initial.

Supposons maintenant que cette affirmation soit vraie à un certain moment pendant l’exécution de l’algorithme. Il y a deux cas :

  • Soit la file de priorité est vide, auquel cas l’algorithme s’arrête et la propriété reste vraie.

  • Soit un nouveau couple (nœud courant, distance) est extrait de la file de priorité. Nous voulons montrer que la distance extraite est la distance d’un plus court chemin du sommet initial au sommet courant.

    Il faut noter que c’est déjà la longueur d’un chemin dans le graphe. En effet, la distance a été mise à jour à un moment où un autre sommet avait été retiré précédemment. Par hypothèse de récurrence, cela correspondait à un plus court chemin, et les sommets étant voisins, nous obtenons une quantité correspondant à la longueur d’un chemin.

    Ensuite, c’est nécessairement la longueur d’un plus court chemin. En effet, considérons un plus court chemin dans le graphe du sommet initial au sommet courant et notons sommet précédent celui juste avant le sommet courant sur ce chemin. Par définition du plus court chemin, le sous-chemin extrait du sommet initial au sommet précédent est un plus court chemin vers ce sommet. Ce sous-chemin est strictement plus court car il contient une arête de moins (et les arêtes ont des poids strictement positifs). En cas de récurrence, le sommet précédent a déjà été retiré de la file de priorité. Et donc la distance vers le sommet courant a soit été fixée à sa valeur minimale à ce moment-là, soit était déjà là avant (elle ne pouvait pas être inférieure puisqu’elle est la longueur d’un chemin dans le graphe).

    Par récurrence, nous concluons que la propriété est vraie à tout moment de l’algorithme.

Correction

Pour finir de prouver la correction et en même temps avoir la terminaison, il reste à montrer que :

  • Chaque sommet ne peut être retiré qu’une seule fois de la file de priorité. Cela se déduit directement de l’augmentation des distances prouvée dans la récurrence précédente.

  • Tout sommet accessible est retiré au moins une fois. Nous remarquons que tout sommet accessible admet un plus court chemin, et nous procédons par récurrence le long de ce chemin.

2.2 — Complexité

La complexité de l’algorithme dépend fortement de la file de priorité utilisée. On peut montrer que la complexité $O(|E| + |V| \cdot log(|V|))$ peut être atteinte en utilisant une structure adaptée.

Dans le cas particulier du labyrinthe sur lequel nous travaillons dans PyRat, chaque sommet a au plus 4 voisins. Nous obtenons donc une complexité de $O(|V| \cdot log(|V|))$, puisque $|E|\leq 4|V|$. Comme cette complexité est inférieure à quadratique, elle est tout à fait raisonnable pour notre problème.

Pour aller plus loin

Fibonacci heap.

Une structure de données pour améliorer le temps d’exécution de l’algorithme de Dijkstra.