🎛️ Dijkstra en action
Le départ est A, la cible est H. Clique sur « Étape » pour voir l'algorithme explorer le graphe sommet par sommet. Les distances minimales se mettent à jour en temps réel.
Étape
0
Sommet en cours
—
Distance A→H
∞
Démarre avec A à distance 0, tous les autres à ∞. Clique « Étape » pour explorer.
☕ 1956 : Dijkstra et son café à Amsterdam
Edsger Wybe Dijkstra (1930-2002), informaticien néerlandais, raconte lui-même la naissance de son algorithme : un matin de 1956, dans un café d'Amsterdam, il devait montrer à des journalistes ce que l'ARMAC (un des premiers ordinateurs hollandais) savait faire. Il a choisi de calculer le plus court chemin entre deux villes des Pays-Bas.
Il dit avoir conçu l'algorithme en 20 minutes, sans papier ni crayon. Publié seulement en 1959 dans un article de 3 pages, c'est devenu l'un des algorithmes les plus utilisés au monde.
🎯 Le problème : chemin de poids minimum
Soit un graphe pondéré (chaque arête a un poids ≥ 0, par exemple distance ou temps). Étant donné un sommet de départ s, on veut trouver le chemin de poids total minimum vers chaque autre sommet.
🧠 L'idée centrale : exploration par distance croissante
Dijkstra maintient deux ensembles : les sommets « définitifs » (distance minimale connue avec certitude) et les sommets « en attente » (avec une estimation provisoire). À chaque étape :
- Choisir le sommet en attente avec la plus petite estimation.
- Le marquer comme définitif.
- Pour chacun de ses voisins encore en attente, relâcher :
si dist[u] + poids(u, v) < dist[v], alors dist[v] = dist[u] + poids(u, v). - Recommencer jusqu'à ce que la destination soit marquée définitive.
Pseudo-code
dist[s] = 0; dist[v] = ∞ pour tout v ≠ s
Q = ensemble de tous les sommets
tant que Q non vide :
u = sommet de Q minimisant dist[u]
retirer u de Q
pour chaque voisin v de u :
si dist[u] + poids(u,v) < dist[v] :
dist[v] = dist[u] + poids(u,v)
prédécesseur[v] = u
🛡️ Pourquoi ça marche : invariant de Dijkstra
Quand on retire un sommet u du tas (avec la plus petite estimation), cette estimation est en fait la vraie distance minimale. Preuve intuitive : tout autre chemin vers u devrait passer par un sommet encore dans Q (donc avec dist ≥ dist[u]) plus une arête de poids positif. Donc plus long. C'est la condition de poids positifs ou nuls qui rend Dijkstra correct.
Pour des poids négatifs, Dijkstra peut se tromper. On utilise alors Bellman-Ford (1958, plus lent : O(VE)) ou Johnson (combine les deux pour tous les paires).
⚡ Complexité : O((V + E) log V)
Avec une bonne implémentation (file de priorité = tas binaire), Dijkstra tourne en O((V + E) log V) où V = sommets, E = arêtes. Pour un graphe routier européen (~50 millions de sommets, ~150 millions d'arêtes), c'est calculé en quelques millisecondes.
Avec un tas de Fibonacci (Fredman-Tarjan 1984), on tombe à O(E + V log V). Cool en théorie, mais en pratique le tas binaire est plus rapide à cause des constantes cachées.
🚀 Applications massives
- GPS et navigation : Google Maps, Waze, Apple Plans, TomTom, et OpenStreetMap utilisent tous des variantes de Dijkstra (souvent enrichies par A* avec heuristique géographique).
- Routage Internet : protocole OSPF (Open Shortest Path First), utilisé par la plupart des routeurs IP, calcule les routes optimales via Dijkstra. Le protocole IS-IS (utilisé par les FAI tier-1) aussi.
- Jeux vidéo : pathfinding des PNJ, IA des stratégies. StarCraft, Civilization, Age of Empires, Minecraft, GTA — tous reposent sur Dijkstra ou A* (variante).
- Robotique : robots autonomes, drones, voitures autonomes. Planification de trajectoires dans un espace discrétisé.
- Réseaux sociaux : calcul de la « distance » entre deux personnes (théorie des 6 degrés). LinkedIn affiche ton chemin vers n'importe quel contact.
- Réseaux téléphoniques : routage des appels en passant par les centraux les moins chargés.
- Logistique : optimisation des tournées de livraison (UPS, FedEx, Amazon), planification de vols, ordonnancement de tâches.
- Biologie : alignement de séquences ADN, plus court chemin dans des arbres phylogénétiques, repliement de protéines.
- Finance : détection d'arbitrages dans des graphes de devises (combiné avec Bellman-Ford pour les cycles négatifs).
- Compilateurs : optimisation de code, analyse de flot de données.
🚀 Variantes et améliorations
- A* (Hart, Nilsson, Raphael 1968) : ajoute une heuristique (par exemple distance à vol d'oiseau vers la cible) pour guider la recherche. Beaucoup plus rapide dans les graphes géographiques.
- Bidirectionnel : lance deux Dijkstra simultanément, l'un depuis A, l'autre depuis B, et s'arrête quand ils se rencontrent. Divise par 2 le temps en moyenne.
- Contraction Hierarchies (2008, université de Karlsruhe) : précalcul du graphe routier qui rend les requêtes 10 000× plus rapides. Utilisé par OpenStreetMap.
- ALT (A* + Landmarks + Triangle inequality) : heuristique sophistiquée pour les graphes très grands.
- Multi-objectif : trouver le compromis entre temps/distance/péage. NP-difficile en général, mais approximé en pratique.
🎓 Dijkstra l'homme : un esprit caustique
Dijkstra ne s'est pas arrêté à son algorithme. Il a obtenu le prix Turing en 1972 (équivalent Nobel pour l'informatique). Il est aussi l'auteur de citations légendaires :
- « Le test de programmes peut prouver la présence de bugs, jamais leur absence. »
- « La question de savoir si un ordinateur peut penser n'est pas plus intéressante que celle de savoir si un sous-marin peut nager. »
- « GO TO considered harmful » (1968) — article qui a éliminé l'instruction goto de la programmation moderne.
- « Beauté est notre métier » (devise du Eindhoven Computer Science department).
📐 Le lien avec ton programme
- Algorithmique : Dijkstra est l'archétype des algorithmes gloutons (greedy) qui font à chaque étape le choix localement optimal et obtiennent l'optimum global. C'est l'une des stratégies algorithmiques fondamentales.
- Récurrence et invariants : la preuve de correction repose sur un invariant de boucle, technique vue en démonstration par récurrence (programme TS).
- Files de priorité : structure de données vue en prépa info.
- Inégalités triangulaires : la propriété d(s, v) ≤ d(s, u) + poids(u, v) est l'analogue graphe de l'inégalité triangulaire en géométrie.
- Optimisation : Dijkstra est un cas particulier de programmation dynamique sur graphe acyclique. Concept central de la recherche opérationnelle.