algorithme de Warshall

Imaginez trois villes A, B et C reliées par des routes à sens unique. Aller directement de A à C coûte 10, mais passer par B ne coûte que 3 + 2 = 5. L’algorithme de Floyd-Warshall répète cette comparaison pour chaque ville susceptible de servir d’étape.

Il conserve, dans une matrice, la meilleure distance connue pour chaque départ et chaque arrivée. À la fin, toutes les paires de sommets ont été examinées, pas seulement celles qui partent d’un sommet choisi.

L’algorithme de Floyd-Warshall est une méthode de programmation dynamique qui calcule la longueur d’un plus court chemin pour chaque paire de sommets d’un graphe pondéré. Le graphe peut être orienté ou non. Une arête absente reçoit la valeur +∞, tandis que la distance d’un sommet à lui-même est initialisée à 0. Les poids négatifs sont admis à condition qu’aucun cycle de poids total négatif ne rende les distances indéfinies.

On numérote les sommets de 1 à n. La valeur D^(k)_ij désigne la meilleure distance connue du sommet i au sommet j lorsque seuls les sommets 1 à k peuvent être utilisés comme intermédiaires. À l’étape k, la méthode compare le chemin déjà connu au chemin qui passe par le sommet k. Cette succession de sous-problèmes explique la programmation dynamique et la complexité O(n³).

Dans son sens strict, l’algorithme de Warshall calcule plutôt la fermeture transitive d’un graphe par des valeurs booléennes : il répond à la question « existe-t-il un chemin ? ». Floyd-Warshall étend le même schéma aux distances pondérées.

Pour chaque sommet intermédiaire k, puis pour chaque départ i et chaque arrivée j, on remplace la distance courante par la plus petite des deux valeurs suivantes : le meilleur trajet déjà connu, ou le trajet allant de i à k puis de k à j.

Après le traitement du n-ième sommet, la matrice contient toutes les distances minimales, si aucun cycle négatif n’est accessible sur les trajets considérés.

La méthode s’applique à un graphe fini dont chaque arête porte un poids numérique. Il faut connaître les n sommets, les arêtes et leurs poids, puis fixer une convention pour l’absence d’arête, généralement +∞. Le résultat recherché est une matrice de n lignes et n colonnes donnant une distance pour chaque couple ordonné de sommets.

Les poids peuvent être négatifs, mais un cycle de poids total négatif empêche de définir un plus court chemin : chaque nouveau tour de cycle diminue encore le coût. Si le graphe est immense et clairsemé, ou si un seul sommet de départ intéresse le calcul, un algorithme à source unique est souvent préférable afin d’éviter les n³ comparaisons.

Considérons trois sommets A, B et C. Les arcs orientés portent les poids A→B = 3, A→C = 10, B→C = 2 et C→A = 4. Une absence d’arc vaut +∞ et chaque distance d’un sommet à lui-même vaut 0.

La matrice initiale, dont les lignes donnent le départ et les colonnes l’arrivée dans l’ordre A, B, C, est :

1. Avec A comme intermédiaire, C atteint B avec un coût 4 + 3 = 7. Après le traitement de A, la matrice est :2. Avec B comme intermédiaire, A atteint C avec un coût 3 + 2 = 5, inférieur à 10. Après le traitement de B, elle devient :

3. Avec C comme intermédiaire, B atteint A avec un coût 2 + 4 = 6. Après le traitement de C, la matrice finale est :Le contrôle est direct : A→C vaut bien 5 par B, C→B vaut 7 par A et B→A vaut 6 par C ; aucun autre détour n’abaisse ces valeurs.

Pour comparer les trajets possibles dans un petit réseau routier orienté, on place les coûts directs dans une matrice, puis on laisse l’algorithme tester chaque carrefour comme étape. Si un seul point de départ importe et que tous les coûts sont non négatifs, Dijkstra évite de calculer les autres départs.

Dans un réseau de dépendances, on peut employer le schéma de Warshall avec des valeurs vrai ou faux pour savoir quels éléments sont accessibles. On choisit cette version booléenne lorsqu’aucune longueur n’est à minimiser.

Pour reconstruire les chemins et pas seulement leurs longueurs, on conserve en parallèle le prochain sommet à suivre pour chaque paire. La matrice des distances seule ne fournit pas la succession des arcs.

Warshall et Floyd-Warshall. Le premier calcule une accessibilité booléenne ; le second minimise des sommes de poids. Entre A et C, Warshall répond « accessible », tandis que Floyd-Warshall donne ici la distance 5.

Floyd-Warshall et Dijkstra. Floyd-Warshall traite toutes les paires et accepte des poids négatifs sans cycle négatif. Dijkstra part d’une seule source et exige des poids non négatifs ; il convient mieux si seules les distances depuis A sont demandées.

Plus court chemin et nombre minimal d’arcs. Un chemin de deux arcs peut coûter moins qu’un arc direct. Dans l’exemple, A→B→C utilise deux arcs mais coûte 5, contre 10 pour A→C.

Cycle négatif. Si une valeur de la diagonale devient strictement négative après le calcul, un cycle négatif est atteignable depuis ce sommet. Il n’existe alors pas de distance minimale finie pour les paires pouvant entrer dans ce cycle puis en sortir.

Sommets non reliés. Une valeur finale +∞ signifie qu’aucun chemin orienté ne relie la paire concernée. Il ne faut ni remplacer +∞ par 0, ni conclure que les deux sommets se confondent.

Ordre des boucles. Le sommet intermédiaire k doit former la boucle extérieure. Changer cet ordre dans une mise à jour en place peut utiliser des sous-problèmes qui ne correspondent plus à l’étape annoncée et produire un résultat erroné.

Coût cubique. Avec n sommets, le nombre de comparaisons croît comme n³ et la matrice occupe un espace proportionnel à n². Pour un grand graphe clairsemé, il faut comparer ce coût à des calculs répétés depuis les seules sources utiles.

Le schéma de mise à jour de Floyd-Warshall est un exemple particulièrement lisible de programmation dynamique : chaque nouvelle matrice réutilise des solutions déjà établies pour un ensemble plus restreint de sommets intermédiaires.

Le même patron dépasse les seules distances : en remplaçant l’addition et le minimum par d’autres opérations compatibles, il peut exprimer l’accessibilité ou d’autres problèmes de chemins. Cette lecture algébrique éclaire la parenté entre Warshall et Floyd-Warshall.