Problème — Un graphe sans circuit : les plus courts et les plus longs chemins

1. Le principe. Si l'on traite les sommets dans un ordre topologique, alors tout prédécesseur d'un sommet est traité avant lui. Au moment où l'on relâche les arcs sortants de $u$, la valeur $d[u]$ est donc déjà définitive : aucun arc ne pourra plus l'améliorer. Un seul passage suffit.

(* Plus courts chemins depuis s dans un graphe ORIENTE ACYCLIQUE pondere.
   g.(u) est la liste des couples (voisin, poids), poids quelconques.
   Precondition : g est acyclique.  Complexite : Theta(n + m). *)
let chemins_dag g s =
  let n = Array.length g in
  let d = Array.make n infinity in
  d.(s) <- 0.0;
  (* INVARIANT : quand on traite u, d.(u) est definitif -- tous ses
     predecesseurs ont deja ete traites. *)
  List.iter (fun u ->
    if d.(u) < infinity then
      List.iter (fun (v, p) ->
        if d.(u) +. p < d.(v) then d.(v) <- d.(u) +. p) g.(u))
    (tri_topologique g);
  d

Le test if d.(u) < infinity n'est pas décoratif : sans lui, on calculerait $\infty +p$, qui vaut $\infty$ en flottant mais déborderait avec un entier sentinelle. Il évite aussi de propager depuis les sommets inaccessibles.

Aucune positivité n'est requise, et c'est la différence avec Dijkstra : l'argument n'est plus « le minimum courant est définitif » mais « les prédécesseurs sont traités avant » — une propriété de l'ordre, pas des poids.