Reconstruire le chemin

let dijkstra_peres adj depart =
  let n = Array.length adj in
  let infini = 1_000_000 in
  let dist = Array.make n infini and pere = Array.make n (-1) in
  let traite = Array.make n false in
  dist.(depart) <- 0;
  for _i = 0 to n - 1 do
    let u = ref (-1) in
    for v = 0 to n - 1 do
      if not traite.(v) && dist.(v) < infini
         && (!u = -1 || dist.(v) < dist.(!u)) then u := v
    done;
    if !u <> -1 then begin
      traite.(!u) <- true;
      List.iter (fun (v, poids) ->
        if dist.(!u) + poids < dist.(v) then begin
          dist.(v) <- dist.(!u) + poids;
          pere.(v) <- !u
        end
      ) adj.(!u)
    end
  done;
  (dist, pere)

let chemin adj depart arrivee =
  let (dist, pere) = dijkstra_peres adj depart in
  if dist.(arrivee) >= 1_000_000 then None
  else
    let rec remonte s =
      if s = depart then [depart] else remonte pere.(s) @ [s]
    in
    Some (remonte arrivee)

À chaque relâchement réussi, on note le prédécesseur pere.(v) <- u. On reconstruit le chemin en remontant les pères — exactement comme pour le BFS (chapitre 15) et la programmation dynamique (chapitre 13).