Probleme – 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.

2. Les plus longs chemins. Il suffit de remplacer < par > et infinity par neg_infinity. Rien d'autre.

Mesure sur le graphe acyclique d'arcs $0\to 1$ (5), $0\to 2$ (3), $1\to 2$ (2), $1\to 3$ (6), $2\to 3$ (7), $2\to 4$ (4), $2\to 5$ (2), $3\to 4$ ($-1$), $3\to 5$ (1), $4\to 5$ ($-2$) :

ordre topologique : 0 1 2 3 4 5
plus courts depuis 0 : 0  5  3  10   7   5
plus longs  depuis 0 : 0  5  7  14  13  15

Une énumération exhaustive confirme : il y a $10$ chemins de $0$ à $5$, le plus court pèse $5$ et le plus long $15$. Noter la présence de poids négatifs, que Dijkstra n'aurait pas supportés.

3. La contradiction n'en est pas une. Le chapitre chap:dynamique met en garde contre le plus long chemin simple dans un graphe quelconque, et le déclare np-difficile. Deux mots font toute la différence.

• « simple ». Dans un graphe acyclique, tout chemin est simple d'office — repasser par un sommet exigerait un circuit. La contrainte globale qui cassait la sous-structure optimale disparaît, parce que la structure du graphe la garantit gratuitement.
• « quelconque ». Dans un graphe avec circuits, un plus long chemin non simple n'existe même pas : on tourne indéfiniment. Il faut donc exiger « simple », et c'est cette exigence qui coûte.

Autrement dit : ce n'est pas la maximisation qui est difficile, c'est la contrainte de simplicité. La preuve en est ici même — la même boucle, le même coût $\Theta (n+m)$, calcule le minimum et le maximum sans que rien ne change.

Une application classique : l'ordonnancement de projet. Les sommets sont des tâches, les arcs des dépendances pondérées par les durées ; le plus long chemin depuis le début est le chemin critique, celui dont tout retard retarde le projet entier. On le calcule en $\Theta (n+m)$ par ces cinq lignes — c'est la méthode pert, et elle n'est rien d'autre que le tri topologique du chapitre lu à l'envers.