Calculateur Floyd-Warshall

Pseudocode

Trois boucles imbriquées et une seule ligne de mise à jour. Toute la subtilité réside dans l'ordre des boucles: k doit être la boucle la plus externe, et se tromper là-dessus est le bogue classique.

FloydWarshall(graphe):
    dist = matrice V par V, tout a l infini
    pour chaque sommet v:     dist[v][v] = 0
    pour chaque arete (u,v,w): dist[u][v] = w

    pour k dans sommets:            // intermediaire
        pour i dans sommets:        // source
            pour j dans sommets:    // cible
                si dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
                    suiv[i][j] = suiv[i][k]   // reconstruction

    // Cycle negatif ssi dist[v][v] < 0 pour un v

L'invariant est qu'après l'itération pour k, dist[i][j] est le plus court chemin de i à j n'utilisant que les k premiers sommets comme intermédiaires. Il faut que k soit la boucle externe pour que cela tienne: c'est elle qui élargit d'un cran à la fois l'ensemble des escales autorisées. Placer k à l'intérieur termine tout de même et produit des nombres plausibles, ce qui rend précisément ce bogue si difficile à repérer.

Exemple détaillé, étape par étape

Exécute Floyd-Warshall sur un petit graphe orienté et observe une entrée s'améliorer deux fois à mesure que l'ensemble des intermédiaires autorisés grandit.

Graphe d'exemple: Arêtes orientées A vers B (3), A vers C (8), B vers C (2), B vers D (7) et C vers D (1).

1. Initialiser. Uniquement les arêtes directes. Depuis A: B vaut 3, C vaut 8, D est inatteignable. Depuis B: C vaut 2, D vaut 7. Depuis C: D vaut 1. Toute la diagonale vaut 0.
2. k = A. Rien ne change. Aucune arête ne pointe vers A, donc dist[i][A] est infini pour tout autre i et aucun chemin ne peut transiter par A.
3. k = B. Deux améliorations. dist[A][C] passe de 8 à dist[A][B] + dist[B][C] = 3 + 2 = 5. dist[A][D] passe de l'infini à 3 + 7 = 10, la première route finie de A vers D.
4. k = C. Deux autres. dist[A][D] s'améliore de nouveau, de 10 à dist[A][C] + dist[C][D] = 5 + 1 = 6, et note que cela utilise la valeur de dist[A][C] que la passe k = B vient d'améliorer. dist[B][D] passe de 7 à 2 + 1 = 3.
5. k = D. Rien ne change, puisque D n'a aucune arête sortante et ne peut servir d'intermédiaire.

Les distances finales depuis A sont B 3, C 5, D 6. L'entrée A vers D s'est améliorée deux fois, de l'infini à 10 puis à 6, ce qui montre directement la stratification: la passe k = C n'a pu trouver la meilleure route que parce que la passe k = B avait déjà amélioré A vers C. Cette dépendance est la raison pour laquelle k doit être la boucle externe.

Complexité et son origine

Temps: O(V^3) · Espace: O(V^2)

Trois boucles imbriquées sur tous les sommets donnent exactement V au cube itérations, chacune effectuant un travail constant. Il n'y a ni sortie anticipée ni dépendance au nombre d'arêtes, l'algorithme coûte donc autant sur un graphe creux que sur un graphe dense. L'espace est la matrice V par V des distances, plus une seconde matrice si tu veux reconstruire les chemins et pas seulement leurs longueurs. En pratique V au cube reste acceptable jusqu'à quelques milliers de sommets; à 5 000 cela représente 125 milliards d'opérations, et lancer Dijkstra depuis chaque sommet, en O(V·E·log V), devient le meilleur choix sur les graphes creux.

Quand utiliser Algorithme de Floyd-Warshall, et quand l'éviter

Floyd-Warshall l'emporte sur la densité et la simplicité, et perd nettement sur les grands graphes creux.

Pièges fréquents

• Placer la boucle k ailleurs qu à l extérieur. C'est le bogue emblématique de Floyd-Warshall. Avec k à l'intérieur, l'invariant tombe et le résultat est silencieusement trop grand pour certaines paires. Aucune erreur n'est signalée et tout paraît raisonnable, si bien que le défaut survit à des tests superficiels. L'ordre doit être k, puis i, puis j.
• Additionner sur l infini. Si l'infini est représenté par un grand entier, dist[i][k] + dist[k][j] déborde et devient négatif, créant des plus courts chemins qui n'existent pas. Protège l'addition, ou utilise une sentinelle assez petite pour que son doublement ne déborde pas.
• L exécuter sans vérifier les cycles négatifs. L'algorithme n'échoue pas, il renvoie simplement des valeurs dénuées de sens. Après les boucles, tout sommet dont dist[v][v] est inférieur à zéro appartient à un cycle négatif. Vérifie-le avant de faire confiance à la matrice.
• L utiliser sur un grand graphe creux. V au cube ignore complètement E. Sur un graphe de 10 000 sommets et 30 000 arêtes, Floyd-Warshall effectue mille milliards d'opérations là où Dijkstra depuis chaque sommet en fait quelques centaines de millions.
• Oublier d initialiser la diagonale. dist[v][v] doit démarrer à 0, pas à l'infini. La laisser infinie casse les toutes premières relaxations et corrompt silencieusement tout ce qui suit.

Questions fréquentes

À quoi sert l'algorithme de Floyd-Warshall?

Il calcule les plus courts chemins entre toutes les paires de sommets d'un graphe pondéré en une seule exécution. Il sert aux tables de distances entre toutes les paires en planification d'itinéraires, au calcul de la fermeture transitive d'une relation, à la recherche du diamètre d'un graphe, à la détection d'arbitrage sur toutes les paires de devises simultanément, et plus généralement dès que tu interrogeras de nombreuses paires source-cible différentes.

Quelle est la complexité temporelle de Floyd-Warshall?

O(V au cube) en temps et O(V au carré) en espace, sans aucune dépendance au nombre d'arêtes. Trois boucles imbriquées parcourent tous les sommets avec un travail constant à l'intérieur, et il n'y a pas de terminaison anticipée. Cela le rend insensible à la densité, ce qui est un avantage sur les graphes denses et un sérieux inconvénient sur les graphes creux.

Pourquoi k doit-il être la boucle la plus externe?

Parce que k représente l'ensemble des sommets autorisés comme intermédiaires, et l'algorithme fait croître cet ensemble un sommet à la fois. Après la passe pour un k donné, chaque entrée est correcte en n'utilisant que les k premiers sommets comme escales. Si k n'est pas à l'extérieur, cet invariant n'est jamais vérifié et l'algorithme renvoie des distances trop grandes sans la moindre erreur.

Floyd-Warshall gère-t-il les poids négatifs?

Oui, les arêtes négatives ne posent pas de problème tant qu'il n'y a pas de cycle négatif. À la fin, une valeur négative sur la diagonale, c'est-à-dire dist[v][v] inférieur à zéro, signifie que v appartient à un cycle négatif et que les distances qui l'impliquent sont dénuées de sens.

Quand utiliser Dijkstra plutôt que Floyd-Warshall?

Quand le graphe est creux et les poids positifs ou nuls. Lancer Dijkstra depuis chaque sommet coûte O(V·E·log V), ce qui sur un graphe comptant bien moins de V au carré arêtes est radicalement plus rapide que V au cube. Floyd-Warshall l'emporte sur les graphes denses, les petits graphes, et quand tu veux l'implémentation la plus courte possible.