Floyd-Warshall (toutes les paires)

let floyd cout =
  let n = Array.length cout in
  let infini = 1_000_000 in
  let d = Array.make_matrix n n 0 in
  for i = 0 to n - 1 do
    for j = 0 to n - 1 do d.(i).(j) <- cout.(i).(j) done
  done;
  for k = 0 to n - 1 do
    for i = 0 to n - 1 do
      for j = 0 to n - 1 do
        if d.(i).(k) < infini && d.(k).(j) < infini
           && d.(i).(k) + d.(k).(j) < d.(i).(j) then
          d.(i).(j) <- d.(i).(k) + d.(k).(j)
      done
    done
  done;
  d

C'est de la programmation dynamique (chapitre 13) sur les graphes : d.(i).(j) devient le plus court chemin de i à j n'empruntant que des sommets intermédiaires < k+1 ; la boucle sur k (la plus externe) autorise un intermédiaire de plus à chaque fois. Coût $\Theta (n^3)$ ; gère les poids négatifs (sans cycle négatif). La garde évite de « passer par l'infini ».