Parcours de graphes et plus courts chemins

Le programme précise le procédé : « tri topologique d'un graphe orienté acyclique à partir de parcours en profondeur ». La règle est d'une simplicité déconcertante : on empile un sommet quand on a fini de le traiter, et l'ordre topologique est la pile lue de haut en bas.

(* Ordre topologique de g. Précondition : g est acyclique.
   Complexité : Theta(n + m). *)
let tri_topologique g =
  let n = Array.length g in
  let vu = Array.make n false in
  let ordre = ref [] in
  let rec visiter u =
    vu.(u) <- true;
    List.iter (fun v -> if not vu.(v) then visiter v) g.(u);
    ordre := u :: !ordre          (* APRÈS les descendants : c'est le postfixe *)
  in
  for s = 0 to n - 1 do if not vu.(s) then visiter s done;
  !ordre

« On peut évoquer la recherche de cycle, la bicolorabilité d'un graphe, la recherche de plus courts chemins dans un graphe à distance unitaire. » La bicolorabilité s'obtient en coloriant alternativement au fil d'un parcours en largeur : si une arête relie deux sommets de même couleur, il existe un cycle impair, et le graphe n'est pas biparti — c'est la réciproque annoncée au chapitre chap:graphes, et elle est ici effective, en $\Theta (n+m)$.

On maintient une estimation $d[v]$ de chaque distance, initialement $+\infty$ sauf $d[s]=0$. À chaque tour, on extrait le sommet non traité d'estimation minimale, on le déclare définitif, et l'on relâche ses arcs sortants.

(* Distances minimales depuis s. g.(u) est la liste des couples (voisin, poids).
   Précondition : tous les poids sont >= 0. Complexité : O((n + m) log n). *)
let dijkstra g s =
  let n = Array.length g in
  let d = Array.make n infinity in
  let fige = Array.make n false in
  let f = file_priorite_vide () in
  d.(s) <- 0.0;
  inserer f (0.0, s);
  while not (est_vide f) do
    let (_, u) = extraire_min f in
    if not fige.(u) then begin
      fige.(u) <- true;                       (* u est DÉFINITIF *)
      List.iter (fun (v, p) ->
        if d.(u) +. p < d.(v) then begin
          d.(v) <- d.(u) +. p;                (* relâchement *)
          inserer f (d.(v), v)
        end) g.(u)
    end
  done;
  d

Le programme demande précisément cette forme : « on présente l'algorithme de Dijkstra avec une file de priorité et en lien avec la représentation de graphes par listes d'adjacences ».

Trois boucles imbriquées, et la récurrence du chapitre chap:dynamique : $D[u][v]$ s'améliore si passer par $k$ est plus court.

/* Remplace d par la matrice des distances minimales entre tous les couples.
   Précondition : d[u][v] est le poids de l'arc u->v, INFINI s'il n'existe pas,
   et d[u][u] = 0. Complexité : Theta(n³). */
void floyd_warshall(double d[][N_MAX], int n) {
    for (int k = 0; k < n; k = k + 1) {          /* LE SOMMET INTERMÉDIAIRE */
        for (int u = 0; u < n; u = u + 1) {
            for (int v = 0; v < n; v = v + 1) {
                if (d[u][k] + d[k][v] < d[u][v]) {
                    d[u][v] = d[u][k] + d[k][v];
                }
            }
        }
    }
}