Adloun

Longueur d'un chemin

Exercice · OCaml (option informatique), chapitre 16 — Plus courts chemins : Dijkstra

Énoncé

Écrire longueur adj chemin : la somme des poids le long d'un chemin donné (liste de sommets), ou failwith si une arête manque.

Corrigé

let rec poids_arc adj u v =
  match adj.(u) with
  | [] -> failwith "arête absente"
  | (w, p) :: reste -> if w = v then p else poids_arc_liste reste v
and poids_arc_liste l v =
  match l with
  | [] -> failwith "arête absente"
  | (w, p) :: reste -> if w = v then p else poids_arc_liste reste v

let rec longueur adj chemin =
  match chemin with
  | [] | [_] -> 0
  | u :: (v :: _ as reste) -> poids_arc adj u v + longueur adj reste

On additionne le poids de chaque arête consécutive du chemin. Le motif u :: (v :: _ as reste) (chapitre 9) donne les deux premiers sommets et la queue.

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.