Dijkstra

let dijkstra adj depart =
  let n = Array.length adj in
  let infini = 1_000_000 in
  let dist = Array.make n infini 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 dist.(v) <- dist.(!u) + poids
      ) adj.(!u)
    end
  done;
  dist

À chaque tour on fige le sommet non traité le plus proche, puis on relâche ses voisins. Les sommets inatteignables conservent infini.