L'ordre des boucles de Floyd-Warshall : le contre-exemple minimal

Il tient en quatre sommets et trois arcs, tous de poids $1$ : $0\to 1$, $1\to 3$, $3\to 2$.

Mesures, première ligne de la matrice ($D[0][\cdot ]$) :

ordre (k, u, v) -- k EXTERNE :   0   1   3   2
ordre (u, v, k) -- k INTERNE :   0   1  inf  2
ordre (u, k, v)              :   0   1   3   2

Avec $k$ à l'intérieur, $D[0][2]$ reste inf : l'algorithme ne trouve pas le chemin $0\to 1\to 3\to 2$, qui existe pourtant et vaut $3$.

Pourquoi. Avec $k$ interne, la case $(u,v)$ est traitée une seule fois, et définitivement. Pour $(0,2)$, il faudrait déjà connaître $D[0][3]=2$ ; or $(0,3)$ est traité après $(0,2)$, puisque $2<3$. Le chemin est découvert trop tard, et la case n'est plus jamais reconsidérée. Le graphe a été choisi pour cela : ses arcs remontent les indices puis redescendent, ce qui interdit tout ordre de découverte compatible avec un balayage unique.

L'ordre $(u,k,v)$ est faux lui aussi, même s'il donne le bon résultat ici. La recherche exhaustive sur les petits graphes en trouve un contre-exemple à quatre sommets et trois arcs : $0\to 1$, $2\to 3$, $3\to 0$. Un ordre qui passe un test n'est pas un ordre correct : il n'y a qu'un seul ordre juste, et c'est celui que porte la démonstration.

Ce qui rend $k$ externe correct, et c'est toute la récurrence : le tour $k$ suppose la matrice $D_k$ entièrement calculée, et produit $D_{k+1}$ entièrement. Les deux boucles internes balayent une matrice complète, et l'on peut le faire en place parce que $D_k[u][k]=D_{k+1}[u][k]$ et $D_k[k][v]=D_{k+1}[k][v]$ — un chemin optimal passant par $k$ n'a aucune raison de repasser par $k$. C'est ce lemme, et lui seul, qui autorise à écraser la matrice, et c'est aussi lui qui tombe si l'on déplace la boucle.