OCaml (option informatique) · Chapitre 16 · Exercice de TD
Le contre-exemple des poids négatifs
Plus courts chemins : Dijkstra · niveau 2
É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.
Exercices semblables
- Dijkstra corrigé
- Distance entre deux sommets corrigé
- Poids unitaires corrigé
- Reconstruire le chemin corrigé
- Floyd-Warshall (toutes les paires) corrigé