Chemins de longueur 2

let chemins_deux m =
  let n = Array.length m in
  let r = Array.make_matrix n n 0 in
  for i = 0 to n - 1 do
    for j = 0 to n - 1 do
      let c = ref 0 in
      for k = 0 to n - 1 do
        if m.(i).(k) && m.(k).(j) then c := !c + 1
      done;
      r.(i).(j) <- !c
    done
  done;
  r

Un chemin de longueur $2$ de i à j passe par un sommet intermédiaire k adjacent aux deux : on compte ces k. C'est exactement le carré de la matrice d'adjacence ($r=M^2$) : plus généralement, (M^p).(i).(j) compte les chemins de longueur p. Coût $\Theta (n^3)$ (un produit matriciel).