Distances depuis un sommet

let distances adj depart =
  let n = Array.length adj in
  let dist = Array.make n (-1) in
  let f = Queue.create () in
  dist.(depart) <- 0;
  Queue.push depart f;
  while not (Queue.is_empty f) do
    let s = Queue.pop f in
    List.iter (fun v ->
      if dist.(v) = -1 then begin dist.(v) <- dist.(s) + 1; Queue.push v f end
    ) adj.(s)
  done;
  dist

Le BFS traite les sommets par distance croissante : quand on atteint v pour la première fois, c'est par le plus court chemin, et dist.(v) = dist.(s) + 1. Les sommets inatteignables gardent -1.