Probleme – Floyd-Warshall au-delà des distances

1. La fermeture transitive. On remplace $(\min ,+)$ par $(\vee ,\wedge )$ : au lieu de « le plus court chemin », on calcule « existe-t-il un chemin ».

/* Remplace a par sa fermeture transitive et reflexive : apres l'appel,
   a[u][v] vaut true ssi il existe un chemin de u a v.
   Precondition : a[u][v] vaut true ssi l'arc u->v existe, et a[u][u] = true.
   Complexite : Theta(n^3) en temps, Theta(n^2) en memoire. */
void fermeture(bool a[][N_MAX], int n) {
    for (int k = 0; k < n; k = k + 1) {          /* k TOUJOURS a l'exterieur */
        for (int u = 0; u < n; u = u + 1) {
            for (int v = 0; v < n; v = v + 1) {
                if (a[u][k] && a[k][v]) { a[u][v] = true; }
            }
        }
    }
}

C'est l'algorithme de Warshall, antérieur à celui de Floyd, et c'est la même récurrence : « il existe un chemin de $u$ à $v$ par $\{0,\dots ,k\}$ » se décompose en « il en existe un sans passer par $k$ » ou « il en existe un jusqu'à $k$, puis un depuis $k$ ». On peut remplacer $(\min ,+)$ par n'importe quel semi-anneau : $(\vee ,\wedge )$ donne l'accessibilité, $(\max ,\min )$ donne le chemin le plus large — celui dont l'arc le plus faible est le plus fort —, $(+,\times )$ compte les chemins.

Mesure sur $0\to 1$, $1\to 2$, $2\to 0$, $1\to 3$, $3\to 4$ :

1 1 1 1 1        les sommets 0, 1, 2 forment un circuit : chacun
1 1 1 1 1        atteint les cinq sommets ; 3 n'atteint que 3 et 4 ;
1 1 1 1 1        4 n'atteint que lui-meme.
0 0 0 1 1
0 0 0 0 1

2. Excentricités, diamètre, rayon, centre. Une fois la matrice des distances calculée, tout se lit dessus :

$$\mathrm{exc}(u)=\underset{v}{\max }D[u][v],\mathrm{diam}=\underset{u}{\max }\mathrm{exc}(u),\mathrm{rayon}=\underset{u}{\min }\mathrm{exc}(u),$$

et le centre est l'ensemble des sommets d'excentricité minimale. Mesure sur un graphe non orienté à six sommets, d'arêtes $(0,1,4)$, $(0,2,2)$, $(1,2,1)$, $(1,3,5)$, $(2,3,8)$, $(2,4,10)$, $(3,4,2)$, $(3,5,6)$, $(4,5,3)$ :

matrice des distances       excentricites : 13 10 11 8 10 13
   0   3   2   8  10  13    diametre = 13   (entre 0 et 5)
   3   0   1   5   7  10    rayon    =  8
   2   1   0   6   8  11    centre   = {3}
   8   5   6   0   2   5
  10   7   8   2   0   3
  13  10  11   5   3   0

Noter que $D[0][2]=2$ mais $D[0][1]=3$ alors que l'arête $0-1$ pèse $4$ : le plus court chemin de $0$ à $1$ passe par $2$. La matrice initiale n'est pas la matrice finale, même sur les couples reliés par une arête.

Où c'est utile : le centre d'un réseau est l'endroit où placer un dépôt pour minimiser le pire trajet ; le diamètre mesure la « largeur » du réseau. Ces deux quantités demandent toutes les distances, donc Floyd-Warshall, et non $n$ Dijkstra — sauf sur un graphe très creux, où $n$ Dijkstra coûteraient $O(n(n+m)\log n)$, meilleur que $n^3$ dès que $m=o(n^2/\log n)$.

3. Les circuits négatifs. Après l'exécution, on lit la diagonale : $D[i][i]<0$ signifie qu'il existe un chemin de $i$ à $i$ de poids négatif, c'est-à-dire un circuit absorbant passant par $i$. Mesure sur $0\to 1$ (1), $1\to 2$ ($-1$), $2\to 3$ ($-1$), $3\to 1$ ($-1$) :

diagonale : 0  -3  -3  -6      -> les sommets 1, 2 et 3 sont sur un circuit negatif

Le sommet $0$ garde $D[0][0]=0$ : il n'est sur aucun circuit, même s'il en atteint un.

Deux précautions. D'abord, les valeurs hors diagonale n'ont plus de sens dès qu'un circuit négatif existe — comme pour Bellman-Ford, seul le drapeau se lit. Ensuite, avec des valeurs infinies représentées par un grand entier, $\mathtt{INF}+\mathtt{INF}$ déborde : on teste d[u][k] < INF && d[k][v] < INF avant d'additionner, ou l'on prend des flottants, où $+\infty$ est une valeur légitime. C'est le défaut du chapitre chap:langage-c qui ressurgit ici, dans un algorithme de quatre lignes.