Plus court chemin (reconstruit)

let plus_court_chemin adj depart arrivee =
  let n = Array.length adj in
  let pere = Array.make n (-1) in
  let vu = Array.make n false in
  let f = Queue.create () in
  vu.(depart) <- true;
  Queue.push depart f;
  while not (Queue.is_empty f) do
    let s = Queue.pop f in
    List.iter (fun v ->
      if not vu.(v) then begin
        vu.(v) <- true; pere.(v) <- s; Queue.push v f
      end
    ) adj.(s)
  done;
  if not vu.(arrivee) then None
  else
    let rec remonte s =
      if s = depart then [depart] else remonte pere.(s) @ [s]
    in
    Some (remonte arrivee)

On enregistre, lors du BFS, le pere par lequel chaque sommet a été atteint (sur son plus court chemin). On reconstruit ensuite le chemin en remontant les pères de arrivee jusqu'au depart. Même idée que la reconstruction en programmation dynamique (chapitre 13).