Plus court chemin de Dijkstra

L'algorithme de Dijkstra trouve le plus court chemin entre des nœuds avec des poids d'arêtes non négatifs. De type glouton (greedy), il met à jour les distances par relaxation : d(v) = min(d(v), d(u) + w(u,v)). Sa complexité temporelle est optimisée à O(E + V log V) en utilisant une file d'attente à tas de Fibonacci.

Dijkstra fait croître une frontière depuis le nœud de départ et fixe toujours le nœud non visité le plus proche. Comme chaque poids d'arête est positif ou nul, aucun détour ultérieur ne peut battre un chemin plus court déjà trouvé : une fois un nœud fixé, sa distance est définitive et n'est jamais réexaminée. C'est pourquoi les calculateurs d'itinéraires et les protocoles de routage comme OSPF s'en servent pour calculer des plus courts chemins fiables.

Edsger Dijkstra a conçu l'algorithme en 1956 en une vingtaine de minutes, sans crayon ni papier, en se reposant à la terrasse d'un café d'Amsterdam. Il cherchait un problème de démonstration pour l'ordinateur ARMAC et a choisi l'itinéraire le plus court entre deux villes néerlandaises, Rotterdam et Groningue. Il l'a publié trois ans plus tard dans un article d'à peine trois pages, l'un des résultats les plus cités de l'informatique.