Floyd-Warshall entre toutes les paires

Vous devez parfois trouver le plus court chemin entre chaque paire de nœuds, et pas seulement depuis une source. C'est le problème de tous les couples.

Floyd-Warshall remplit un tableau complet des distances entre tous les couples grâce à trois boucles imbriquées simples et presque aucune initialisation.

Utilisez une matrice où dist[i][j] représente le meilleur coût connu de i à j. Initialisez-la avec les arêtes directes fournies.

Chaque nœud peut atteindre lui-même gratuitement : définissez donc la diagonale dist[i][i] à zéro avant de commencer les relâchements.

L'astuce consiste à autoriser les chemins à passer par un nœud intermédiaire k, puis à vérifier si passer par k coûte moins cher qu'un trajet direct.

La boucle externe est k, le point intermédiaire choisi. Les boucles internes i et j essaient chaque paire avec ce point intermédiaire.

Pour chaque paire, relâchez en passant par k : si le trajet de i à k puis de k à j est plus court, mettez dist[i][j] à jour avec ce coût combiné.

Lorsque k est terminé, toutes les paires peuvent utiliser des nœuds intermédiaires jusqu'à k. Placer k à l'extérieur garantit que cette propriété reste correcte.

Floyd-Warshall accepte les arêtes négatives, mais pas les cycles négatifs. Un cycle négatif laisse au moins une entrée diagonale inférieure à zéro.

Trois boucles sur n nœuds donnent un temps en O(n^3) et un espace en O(n^2), ce qui n'est pratique que lorsque n reste de l'ordre de quelques centaines.

Choisissez Floyd-Warshall lorsque le graphe est petit et dense et que vous avez réellement besoin de la distance entre chaque paire, plutôt que depuis une seule source.

Initialisez une matrice, mettez la diagonale à zéro, puis parcourez k, i, j et relâchez en passant par k. Les plus courts chemins entre tous les couples en O(n^3). 🧮