Floyd-Warshall : plus courts chemins entre toutes les paires

Floyd-Warshall calcule les plus courts chemins entre chaque paire de nœuds d'un graphe pondéré — y compris les graphes avec des arêtes de poids négatif (mais sans cycles négatifs). Exécuter Dijkstra depuis chaque source prend O(V × (V+E) log V) ; Floyd-Warshall s'exécute en O(V³), quelle que soit la densité des arêtes. Pour les graphes denses avec V ≤ 500, Floyd-Warshall est souvent plus simple et offre une rapidité comparable.

L'idée de Floyd-Warshall est la suivante : dp[i][j][k] = plus court chemin de i à j en utilisant uniquement les nœuds {0, 1, ..., k} comme intermédiaires. Soit le plus court chemin utilise le nœud k comme intermédiaire, soit il ne l'utilise pas. Dans le premier cas : dp[i][j][k] = dp[i][k][k-1] + dp[k][j][k-1]. Dans le second : dp[i][j][k] = dp[i][j][k-1]. Comme la troisième dimension ne progresse que vers l'avant, elle peut être supprimée : nous mettons à jour la matrice sur place.

Commencez avec une matrice V×V : dist[i][i] = 0 (distance de zéro vers soi-même), dist[i][j] = weight pour les arêtes directes et dist[i][j] = inf pour les paires sans arête. Parcourez ensuite tous les nœuds intermédiaires k en mettant à jour les paires (i, j). La boucle externe sur k doit être exécutée en premier afin de construire correctement les chemins à travers un ensemble croissant de nœuds intermédiaires autorisés.

Suivons l'exécution de Floyd-Warshall sur un graphe à 4 nœuds. Après le traitement de chaque nœud intermédiaire k, la matrice se complète avec des chemins plus courts passant par le nœud k. L'algorithme gère naturellement les sauts multiples en construisant progressivement les plus courts chemins.

Après l'exécution de Floyd-Warshall, vérifiez la diagonale principale : si un dist[i][i] < 0, un cycle négatif passant par le nœud i existe. En effet, un cycle négatif permet d'atteindre i depuis i avec un coût négatif. Si aucun cycle négatif n'existe, toutes les entrées de la diagonale restent égales à 0.

Pour reconstituer le chemin réel de i à j, maintenez une matrice next[i][j] : initialement, next[i][j] = j pour les arêtes directes. Lors d'une mise à jour via le nœud intermédiaire k, définissez next[i][j] = next[i][k]. Pour récupérer le chemin, partez de i et suivez les pointeurs next jusqu'à atteindre j. Cela ajoute un espace O(V²) et un coût O(V) pour chaque reconstitution de chemin.

Une variante plus simple : la fermeture transitive répond à la question « le nœud j est-il accessible depuis le nœud i ? » pour toutes les paires. Remplacez les distances par des valeurs booléennes : reach[i][j] = reach[i][j] or (reach[i][k] and reach[k][j]). Il s'agit de Floyd-Warshall avec l'opération OR booléenne au lieu de l'addition et du minimum. Initialisez reach[i][i] = True et reach[i][j] = True pour les arêtes directes.

Floyd-Warshall : O(V³) en temps et O(V²) en espace. Pour les graphes denses (E ≈ V²) avec V ≤ 300, il est plus rapide que l'exécution de Dijkstra V fois (également en O(V³) dans ce cas). Pour les graphes creux avec V = 1000 et E = 3000, V exécutions de Dijkstra coûtent O(V×E×log V) ≈ 33M, tandis que Floyd-Warshall coûte O(V³) = 10⁹ : Dijkstra est plus efficace. Sachez choisir l'algorithme approprié dans chaque situation.

Attribuez à toutes les arêtes un poids égal à 1 (ou utilisez une matrice d’adjacence booléenne avec Floyd-Warshall en utilisant une addition plutôt que min) : dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]). Cela calcule le nombre minimal de sauts entre toutes les paires — le résultat d’un BFS entre toutes les paires, mais calculé en un seul parcours de Floyd-Warshall en O(V³).

Floyd-Warshall est souvent abordé lors d’entretiens pour des questions portant sur : (1) les distances entre toutes les paires dans un petit graphe, (2) la recherche d’un cycle dont le poids total est négatif, (3) le calcul de plus courts chemins dans des problèmes de propagation de contraintes et (4) les problèmes demandant explicitement des solutions en O(V³), où V ≤ 200. Mentionnez toujours la structure à trois boucles et la condition d’absence de cycles négatifs pour garantir la correction.

Pour les graphes non orientés, ajoutez les deux directions pour chaque arête : dist[u][v] = dist[v][u] = weight. Le reste de l’algorithme est identique. La matrice obtenue est symétrique : dist[i][j] == dist[j][i] pour toutes les paires. Lors de l’initialisation, veillez à ne pas attribuer accidentellement des arêtes orientées : les arêtes non orientées doivent être ajoutées dans les deux directions à la matrice initiale avant l’exécution des trois boucles.

Testez votre compréhension des concepts de structures de données et d’algorithmes — préparation aux entretiens de programmation de cette leçon.

Dans cette leçon, vous avez appris : Floyd-Warshall calcule les plus courts chemins entre toutes les paires grâce à trois boucles imbriquées et à la récurrence dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]), les cycles de poids négatif sont détectables en vérifiant si une valeur dist[i][i] < 0 existe après l’exécution, et l’algorithme s’exécute en O(V³) et utilise un espace en O(V²). Ensuite, nous reviendrons sur les applications des plus courts chemins avec le problème du délai réseau et les techniques de reconstruction de chemins.