Algorithme de Dijkstra

Votre calculateur d'itinéraire connaît le chemin le plus rapide de votre porte à presque n'importe où. Au cœur de cette idée, il y a un algorithme qu'Edsger Dijkstra a mis au point en une vingtaine de minutes en 1956 : s'étendre depuis le départ, et toujours terminer d'abord l'endroit le plus proche.

Un graphe dont les arêtes ont des longueurs, avec les nœuds proches du départ terminés en vert, un arbre des plus courts chemins et une file de priorité dessinée en dessous
Un graphe dont les arêtes ont des longueurs, avec les nœuds proches du départ terminés en vert, un arbre des plus courts chemins et une file de priorité dessinée en dessous

L'idée

Imaginez des villes reliées par des routes de longueurs différentes. La question est : quel est le plus court chemin de ma ville vers chacune des autres ? Le parcours en largeur y répond quand chaque route compte pareil, mais ici un trajet avec plus de routes peut être plus court. L'algorithme de Dijkstra garde, pour chaque ville, la plus courte distance trouvée jusqu'ici, et fait grandir une région de villes dont la distance est sûre, en ajoutant toujours la ville la plus proche qui n'est pas encore sûre.

Pas à pas

Donnez au départ la distance 0 et à tous les autres nœuds l'infini. Mettez le départ dans une file de priorité, une file qui sort toujours le nœud de plus petite distance. Prenez ce nœud ; sa distance est maintenant définitive. Pour chaque voisin non définitif, calculez la distance en passant par ce nœud : sa distance plus la longueur de l'arête. Si c'est plus court que la distance actuelle du voisin, abaissez-la, retenez ce nœud comme chemin pour y aller, et mettez le voisin dans la file. C'est ce qu'on appelle relâcher une arête. Répétez jusqu'à ce que la file soit vide, ou que la cible en sorte.

Un exemple

Prenons les arêtes A–B de longueur 4, A–C 1, B–C 2, B–D 1, C–D 5 et D–E 3, et partons de A. Prendre A donne à B la distance 4 et à C la distance 1. C est le plus proche, donc il est définitif à 1 ; en passant par C, B descend à 1 + 2 = 3 et D reçoit 1 + 5 = 6. Maintenant B est le plus proche, définitif à 3, et en passant par B, D descend à 3 + 1 = 4. D est définitif à 4 et donne à E 4 + 3 = 7. Le plus court chemin de A à E est donc A → C → B → D → E, de longueur 7, même si A → B → D → E utilise moins d'arêtes et a une longueur de 8.

Pourquoi il est correct

Supposons que le nœud X soit le plus proche dans la file, à distance d. Tout autre chemin du départ à X doit quitter à un moment la région des nœuds définitifs, et le premier nœud qu'il atteint hors de cette région est dans la file, donc déjà à au moins d. La suite du chemin ne peut pas le raccourcir, car aucune arête n'est négative. Donc d est la plus courte distance jusqu'à X. Avec une arête négative, cet argument ne tient plus ; on utilise alors l'algorithme de Bellman–Ford, qui relâche toutes les arêtes encore et encore.

Histoire et usages

Edsger W. Dijkstra a conçu l'algorithme en 1956 pour faire la démonstration d'un nouvel ordinateur, l'ARMAC à Amsterdam, en trouvant des trajets entre des villes néerlandaises, et l'a publié en 1959. La même idée, avec une file plus astucieuse, tourne dans les calculateurs d'itinéraire et dans des protocoles de routage d'Internet comme OSPF et IS-IS, qui calculent le plus court chemin des données entre routeurs. L'algorithme A* ajoute une estimation de la distance restante, ce qui lui permet de se diriger vers la cible et d'examiner moins de nœuds.

Edsger W. Dijkstra au tableau
Edsger W. Dijkstra au tableau

À vous d'essayer

Ouvrez l'application et appuyez sur Étape. Les nombres sur les arêtes sont leurs longueurs, et le nombre sur chaque nœud est sa distance jusqu'ici. Les nœuds dans la file sont bleus, les nœuds définitifs verts, et la file sous le graphe les liste du plus proche au plus éloigné, avec leurs distances. Guettez les moments où une distance baisse parce qu'un trajet qui semblait plus long se révèle plus court, et choisissez une cible pour voir la recherche s'arrêter dès que la cible est définitive.

Questions fréquemment posées

Quelle est la complexité en temps de l'algorithme de Dijkstra ?

Elle dépend de la file de priorité. Avec une simple liste, elle est en O(V²) pour V nœuds ; avec un tas binaire, en O((V + E) log V) pour E arêtes ; avec un tas de Fibonacci, en O(E + V log V), comme l'ont montré Michael Fredman et Robert Tarjan en 1984.

L'algorithme de Dijkstra gère-t-il les poids d'arête négatifs ?

Non. Il suppose que la distance d'un nœud ne peut plus s'améliorer une fois que ce nœud est le plus proche dans la file, ce qu'une arête négative peut contredire. Pour les graphes avec des arêtes négatives, utilisez l'algorithme de Bellman–Ford.

L'algorithme de Dijkstra trouve-t-il le chemin vers chaque nœud ?

Oui. Exécuté jusqu'au bout, il donne la plus courte distance du départ à chaque nœud accessible, et les nœuds retenus forment un arbre des plus courts chemins. S'arrêter dès que la cible est définitive épargne du travail quand un seul chemin est utile.

Quel est le lien entre l'algorithme de Dijkstra et A* ?

L'algorithme A* est l'algorithme de Dijkstra avec un indice : il ordonne la file selon la distance jusqu'ici plus une estimation de la distance restante, comme la distance à vol d'oiseau sur une carte. Avec une bonne estimation, il trouve le même plus court chemin en examinant beaucoup moins de nœuds.

Prêt à l'essayer ?

Ouvrez PictorX dans votre navigateur – aucune installation, aucune carte de crédit requise pour démarrer.

Essayer l'algorithme de Dijkstra