Probleme – Rendre le chemin, pas seulement sa longueur

1. Le parcours en largeur avec pères.

(* Renvoie (d, pere) : d.(v) est la distance en nombre d'arcs (-1 si inaccessible)
   et pere.(v) le sommet depuis lequel v a ete decouvert (-1 pour la source
   et pour les inaccessibles).
   Precondition : 0 <= s < Array.length g.  Complexite : Theta(n + m). *)
let largeur_peres g s =
  let n = Array.length g in
  let d = Array.make n (-1) and pere = Array.make n (-1) in
  let f = Queue.create () in
  d.(s) <- 0; Queue.push s f;
  while not (Queue.is_empty f) do
    let u = Queue.pop f in
    List.iter (fun v ->
      if d.(v) = -1 then begin
        d.(v) <- d.(u) + 1;
        pere.(v) <- u;                 (* on retient QUI a decouvert v *)
        Queue.push v f
      end) g.(u)
  done;
  (d, pere)

(* Chemin de s a v, ou [] si v est inaccessible.
   Precondition : pere provient d'un parcours lance depuis s.
   Complexite : Theta(longueur du chemin). *)
let chemin pere s v =
  let rec remonter v acc =
    if v = s then s :: acc
    else if v = -1 then []             (* inaccessible : on rend la liste vide *)
    else remonter pere.(v) (v :: acc)
  in remonter v []

Mesure sur le graphe à huit sommets du premier exercice :

d    = 0 1 1 2 2 2 3 4
pere = - 0 0 1 1 2 3 6
  0 -> 3 : 0 1 3        0 -> 6 : 0 1 3 6
  0 -> 5 : 0 2 5        0 -> 7 : 0 1 3 6 7

Chaque chemin a bien $d(v)$ arcs.

2. Les deux preuves.

C'est une arborescence. Chaque sommet accessible autre que $s$ reçoit un père une seule fois — la ligne pere.(v) <- u est sous le test d.(v) = -1, qui n'est vrai qu'au premier passage. Le graphe des arcs $(\mathrm{pere}(v),v)$ a donc exactement $n_{\text{acc}}-1$ arcs pour $n_{\text{acc}}$ sommets accessibles. Il est de plus sans cycle : $d(\mathrm{pere}(v))=d(v)-1<d(v)$, donc la fonction $d$ décroît strictement en remontant, et une remontée ne peut pas boucler. Un graphe connexe à $n-1$ arcs et sans cycle est un arbre (chapitre chap:arbres).

Terminaison de chemin. Le variant est $d(v)$ : il décroît strictement de $1$ à chaque remontée, et il est minoré par $0$, atteint exactement en $s$.

Le chemin est de longueur minimale. La suite $v,\mathrm{pere}(v),\dots ,s$ a exactement $d(v)$ arcs par la décroissance ci-dessus, et le théorème du chapitre dit que $d(v)$ est la distance minimale. Le chemin est donc optimal — et non pas seulement « un chemin ».

3. Dijkstra et Floyd-Warshall.

Dijkstra : on écrit pere.(v) <- u dans le relâchement, à côté de la mise à jour de d.(v) — et pas ailleurs. Un sommet peut changer de père plusieurs fois, la dernière valeur étant la bonne, puisque le relâchement final est celui qui a produit la distance définitive. La reconstruction est la même fonction. Mesure sur le graphe pondéré déroulé plus haut : pere = [-;0;0;2;5;2], d'où $0\to 2\to 5\to 4$ pour le sommet $4$.

Floyd-Warshall : il n'y a pas de source, donc pas d'arborescence — il faut une matrice. On maintient $\mathrm{suivant}[u][v]$, le premier sommet après $u$ sur un plus court chemin de $u$ à $v$ :

/* Initialisation : suivant[u][u] = u, suivant[u][v] = v si l'arc u->v
   existe, et -1 sinon. */
if (d[u][k] + d[k][v] < d[u][v]) {
    d[u][v] = d[u][k] + d[k][v];
    suivant[u][v] = suivant[u][k];      /* on part comme pour aller vers k */
}

/* Reconstruction : Theta(longueur du chemin). */
void afficher_chemin(int suivant[][N_MAX], int u, int v) {
    if (suivant[u][v] == -1) { printf("aucun chemin\n"); return; }
    printf("%d", u);
    while (u != v) { u = suivant[u][v]; printf(" %d", u); }
    printf("\n");
}

La ligne à comprendre est suivant[u][v] = suivant[u][k] : puisque le nouveau chemin de $u$ à $v$ commence par aller de $u$ à $k$, son premier pas est celui du chemin de $u$ à $k$. On stocke le premier sommet et non le dernier, ce qui donne une reconstruction dans le bon sens, sans renversement.

Le coût de la reconstruction, dans les trois cas : $\Theta (1)$ de mémoire par sommet (ou par couple), et $\Theta (\text{longueur})$ à la lecture. C'est la même leçon que le chapitre chap:dynamique : on garde la décision, pas la valeur — un tableau d'entiers suffit à retrouver tous les chemins.