Le contre-exemple des poids négatifs
Exercice · OCaml (option informatique), chapitre 16 — Plus courts chemins : Dijkstra
Énoncé
Sur le graphe 0 -> 1 (poids 2), 0 -> 2 (poids 5), 2 -> 1 (poids -4), donner la distance que calcule Dijkstra de 0 à 1, et la vraie.
Corrigé
Dijkstra traite d'abord 0 (relâche : dist.(1) = 2, dist.(2) = 5), puis fige 1 (le plus proche, 2) — définitivement. Il renvoie dist.(1) = 2. Or le vrai plus court chemin est 0 -> 2 -> 1 de coût 5 - 4 = 1. Dijkstra se trompe car il a figé 1 avant de découvrir le détour avantageux par l'arête négative. C'est pourquoi Dijkstra suppose les poids positifs.
Les autres exercices de ce chapitre Le cours du chapitre
Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.