Bellman-Ford (poids négatifs)

let bellman_ford n aretes depart =
  let infini = 1_000_000 in
  let dist = Array.make n infini in
  dist.(depart) <- 0;
  for _i = 1 to n - 1 do                 (* n-1 passes *)
    List.iter (fun (u, v, poids) ->
      if dist.(u) < infini && dist.(u) + poids < dist.(v) then
        dist.(v) <- dist.(u) + poids
    ) aretes
  done;
  dist

On relâche toutes les arêtes, n-1 fois de suite. Comme un plus court chemin a au plus n-1 arêtes, n-1 passes suffisent à propager les bonnes distances. Plus lent que Dijkstra ($\Theta (nm)$) mais il gère les poids négatifs (et une n-ième passe qui améliorerait encore révélerait un cycle de poids négatif).