Floyd-Warshall, matrice après matrice

Mesures (la diagonale est nulle, inf note l'absence de chemin) :

D initiale        apres k = 0       apres k = 1       apres k = 2  (= finale)
  0   3   7 inf     0   3   7 inf     0   3   5 inf     0   3   5   6
inf   0   2 inf   inf   0   2 inf   inf   0   2 inf     7   0   2   3
  5 inf   0   1     5   8   0   1     5   8   0   1     5   8   0   1
  4 inf inf   0     4   7  11   0     4   7   9   0     4   7   9   0

Le tour $k=3$ ne change plus rien.

Lecture des tours.

• Le tour $k=0$ remplit les cases dont le chemin passe par $0$ : $D[2][1]=5+3=8$ (c'est $2\to 0\to 1$) et $D[3][1]=4+3=7$, $D[3][2]=4+7=11$.
• Le tour $k=1$ améliore $D[0][2]$ de $7$ à $5$ ($0\to 1\to 2$, soit $3+2$) et $D[3][2]$ de $11$ à $9$ ($3\to 0\to 1\to 2$).
• Le tour $k=2$ ouvre tout le reste : $D[0][3]=6$ ($0\to 1\to 2\to 3$), $D[1][0]=7$ ($1\to 2\to 0$), $D[1][3]=3$.

L'invariant est visible dans la table : après le tour $k$, la case $D[u][v]$ contient la longueur du plus court chemin de $u$ à $v$ n'utilisant que $\{0,\dots ,k\}$ comme intermédiaires. Après $k=1$, $D[1][0]$ vaut encore inf : le seul chemin de $1$ à $0$ passe par $2$, qui n'est pas encore autorisé. Il apparaît exactement au tour $k=2$.

Contrôle utile en pratique : si, après le dernier tour, une case diagonale est devenue strictement négative, c'est qu'il existe un circuit de poids négatif passant par ce sommet. C'est gratuit — la diagonale est déjà là — et c'est le sujet du problème sur Floyd-Warshall, plus bas.