Plus court chemin de Dijkstra

Observe comment l'algorithme de Dijkstra trouve le plus court chemin dans un graphe pondéré.

Exemple résolu — Plus court chemin de Dijkstra

Nœud 0	0
Nœud 1	3
Nœud 2	8
Nœud 3	2
Nœud 4	8
Plus court chemin	0 → 3 → 4 (cost: 8)

Ce sont les valeurs affichées par le calculateur à l’ouverture de la page. Modifiez une entrée ci-dessus pour les recalculer.

Chargement de la simulation interactive...

La relaxation est tout l’algorithme ; la file de priorité n’est que de la vitesse 🖖

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.

Pourquoi le nœud le plus proche est sûr 🖖

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.

Conçu en vingt minutes autour d'un café 🖖

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.

Problème entièrement résolu

Nœud 1 à une arête de la source pour un coût de 4 5 étapes
Le sommet 1 se trouve à une arête de la source, pour un coût de 4 — et l'algorithme indique une distance de 3. Suivez l'ordre de fixation des sommets et trouvez d'où vient ce 3.
1. Dijkstra fixe les sommets par ordre de distance, sans jamais y revenir. Cet ordre constitue tout l'algorithme et toute sa preuve : lorsqu'un sommet est fixé, aucun chemin plus économique vers celui-ci ne peut exister, car un tel chemin devrait passer par un sommet non encore fixé qui se trouve déjà plus éloigné.
  
  $E = {(0, 1, 4), (0, 3, 2), (1, 2, 5), (1, 3, 1), (2, 4, 3), (3, 4, 6)}$
2. À partir de la source, les deux arêtes directes donnent des distances provisoires de 4 et 2. Aucune n'est encore définitive — ce sont des bornes supérieures.
  
  $settle 0 : d_{1} = 4, d_{3} = 2$
3. Le plus proche est le sommet 3 à 2, il est donc fixé en premier. Relâcher ses arêtes permet de trouver un chemin vers le sommet 1 d'un coût de 2 + 1 = 3, ce qui améliore l'arête directe de 4. C'est cette étape qui répond à la question : le chemin le plus économique vers un voisin n'est pas nécessairement l'arête qui y mène.
  
  $settle 3 (d = 2) : d_{1} = min (4, 2 + 1) = 3, d_{4} = 2 + 6 = 8$
4. Le sommet 1 est fixé à 3, et le relâchement à partir de celui-ci atteint le sommet 2 à 8.
  
  $settle 1 (d = 3) : d_{2} = 3 + 5 = 8$
5. Le sommet 4 est accessible à 8 en passant par le sommet 3, et l'alternative par le sommet 2 coûte 8 + 3 = 11 ; le plus court des deux est donc conservé.
  
  $settle 2, 4 : d_{4} = min (8, 8 + 3) = 8 ⟹ 0 \to 3 \to 4$
Réponse

L'outil affiche des distances de 3, 8, 2, 8 et un plus court chemin de 0 → 3 → 4. La leçon réside dans le sommet 1 : une arête directe n'est pas un plus court chemin, et la fixation gloutonne est ce qui permet de s'en rendre compte à moindre coût plutôt que de façon exponentielle. Cette garantie comporte toutefois une condition — des poids non négatifs. Avec une arête négative, un sommet fixé tôt peut être amélioré par la suite, et la preuve de l'étape 1 s'effondre. Cliquez sur le préréglage d'arête négative et observez l'échec dans les deux sens à la fois : le sommet 3 ressort à −1, ce qui n'est la distance d'aucun trajet, et la reconstruction du chemin abandonne complètement avec « aucun chemin — les prédécesseurs forment une boucle ». Des résultats faux et aucun chemin, pour un algorithme prouvé exact dès lors que chaque poids est non négatif.

$d_{1} = 3 via node 3, not 4 direct; 0 \to 3 \to 4 = 8$

Références (2)

The three-page paper, in which the shortest-path algorithm is the SECOND of the two problems: E. W. Dijkstra, "A note on two problems in connexion with graphs." Numerische Mathematik 1, 269–271, 1959.
The algorithm the negative-edge preset points you to, which tolerates negative weights and detects a negative cycle instead of answering as though there were none: R. Bellman, "On a routing problem." Quarterly of Applied Mathematics 16(1), 87–90, 1958.

Par l’équipe 42Math · Mis à jour 2026-06-11

Vérifié sur des sources publiées. Corrections bienvenues. Politique éditoriale · Corrections

Toutes les leçons : Informatique →

Exemples de problèmes

Ville à 5 nœuds - Ville à 5 nœuds : plus court chemin 0→4
Grille 3×3 - Grille 3×3 : plusieurs plus courts chemins
Profond vs large - Profond contre large : le glouton échoue
Arête négative - Arête négative : Dijkstra peut échouer