OCaml (option informatique) · Chapitre 16 · Exercice de TD
Distance entre deux sommets
Plus courts chemins : Dijkstra · niveau 2
Énoncé
Écrire distance adj a b : int option (None si b est inatteignable).
Corrigé
let distance adj a b =
let dist = dijkstra adj a in
if dist.(b) >= 1_000_000 then None else Some dist.(b)On lance Dijkstra depuis a et on lit la case b. La valeur sentinelle infini (restée inchangée) signale l'inaccessibilité, qu'on traduit en None.
Exercices semblables
- Dijkstra corrigé
- Poids unitaires corrigé
- Le contre-exemple des poids négatifs corrigé
- Reconstruire le chemin corrigé
- Floyd-Warshall (toutes les paires) corrigé