Probleme – Bellman-Ford : ce que Dijkstra ne sait pas faire

1. L'algorithme. Il ne choisit rien : il relâche tous les arcs, $n-1$ fois de suite.

(* Renvoie (d, pere, circuit) : d.(v) est la distance minimale de s a v,
   circuit vaut true si un circuit de poids negatif est accessible depuis s
   (auquel cas d n'a pas de sens).
   Preconditions : arcs est un tableau de (origine, but, poids), 0 <= s < n.
   Complexite : Theta(nm) en temps, Theta(n) en memoire. *)
let bellman_ford n arcs s =
  let d = Array.make n infinity and pere = Array.make n (-1) in
  d.(s) <- 0.0;
  (* INVARIANT : apres le tour k, d.(v) est la longueur minimale d'un chemin
     de s a v utilisant AU PLUS k arcs. *)
  for _ = 1 to n - 1 do
    Array.iter (fun (u, v, p) ->
      if d.(u) +. p < d.(v) then begin d.(v) <- d.(u) +. p; pere.(v) <- u end) arcs
  done;
  (* un tour de plus : s'il ameliore encore, c'est qu'il n'y a pas de minimum *)
  let circuit = Array.exists (fun (u, v, p) -> d.(u) +. p < d.(v)) arcs in
  (d, pere, circuit)

2. La correction.

L'invariant est celui écrit dans le code. Il tient au tour $0$ : le seul chemin à zéro arc est $s$ vers lui-même, de longueur $0$. Supposons-le vrai après le tour $k$, et soit $v$ atteignable par un chemin optimal à $k+1$ arcs, disons $s⇝u\to v$. Le préfixe $s⇝u$ a $k$ arcs, et il est optimal parmi les chemins à $\le k$ arcs (sous-structure optimale). Par hypothèse, $d[u]$ vaut déjà cette valeur avant le tour $k+1$. Comme le tour $k+1$ relâche l'arc $(u,v)$, on obtient $d[v]\le d[u]+p(u,v)$, la valeur voulue. L'invariant tient.

Le nombre de tours. S'il n'y a pas de circuit négatif, un plus court chemin est simple : s'il repassait par un sommet, on pourrait retirer la boucle intermédiaire, dont le poids est $\ge 0$, sans allonger. Un chemin simple a au plus $n-1$ arcs. Après $n-1$ tours, l'invariant donne donc la vraie distance. C'est l'acyclicité des chemins optimaux qui fixe la borne, pas une propriété de l'algorithme.

3. La détection du circuit négatif. On fait un tour de plus. S'il améliore encore une distance, c'est qu'il existe un chemin à $n$ arcs strictement meilleur que tous les chemins à $\le n-1$ arcs — donc un chemin non simple meilleur que sa version simplifiée, donc un circuit de poids strictement négatif sur le trajet.

Mesure sur $0\to 1$ (1), $1\to 2$ ($-1$), $2\to 3$ ($-1$), $3\to 1$ ($-1$) — le circuit $1\to 2\to 3\to 1$ pèse $-3$ :

d = [0; -8; -6; -7]   circuit absorbant : true

Les valeurs de $d$ n'ont aucun sens : en tournant une fois de plus, on les aurait rendues plus petites encore. Le drapeau est la seule information à lire.

Sur le graphe de l'exercice sur les poids négatifs, où il n'y a pas de circuit négatif : d = [0; 1; 5; 2] ; circuit : false — c'est bien la réponse que Dijkstra manquait.

4. La comparaison.

La ligne « nature » est la plus instructive. Dijkstra est un glouton : il fige un sommet et n'y revient jamais, et sa preuve d'échange exige la positivité. Bellman-Ford est de la programmation dynamique : le sous-problème est « la meilleure distance en au plus $k$ arcs », la récurrence est le relâchement, et il n'exige rien — au prix d'un facteur $n/\log n$.

Une optimisation gratuite : si un tour n'améliore aucune distance, tous les suivants sont inutiles, et l'on peut sortir. Sur les graphes réels, Bellman-Ford converge souvent en trois ou quatre tours ; le $n-1$ est la borne du pire cas, pas le coût courant.