Floyd-Warshall entre toutes les paires
Trouver les plus courts chemins entre chaque paire
Floyd-Warshall entre toutes les paires est une leçon Competitive Programming Academy gratuite sur CoddyKit. Ceci est la leçon 4 sur 4. Tu peux lire la leçon complète ci-dessous gratuitement — puis la pratiquer en direct dans le navigateur avec un éditeur de code intégré et un tuteur IA 24/7. Elle fait partie du parcours d'apprentissage Competitive Programming Academy, et ta progression se synchronise sur le web et l'application CoddyKit. Le cours Competitive Programming Academy comprend 4 leçons au total.
Chaque paire à la fois
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.
Découvrez Floyd-Warshall
Floyd-Warshall remplit un tableau complet des distances entre tous les couples grâce à trois boucles imbriquées simples et presque aucune initialisation.
La matrice des distances
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.
dist = [[INF] * n for _ in range(n)]Définir la diagonale
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.
for i in range(n):
dist[i][i] = 0L'idée du nœud intermédiaire
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.
L'ordre des boucles est important
La boucle externe est k, le point intermédiaire choisi. Les boucles internes i et j essaient chaque paire avec ce point intermédiaire.
for k in range(n):
for i in range(n):
for j in range(n):L'étape de relâchement
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é.
if dist[i][k] + dist[k][j] < dist[i][j]:
dist[i][j] = dist[i][k] + dist[k][j]Pourquoi k est à l'extérieur
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.
Les arêtes négatives sont acceptées
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.
Le temps d'exécution
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.
Quand le choisir
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.
Vérification rapide
Quelle boucle doit être la plus externe dans Floyd-Warshall ?
Récapitulatif : Floyd-Warshall
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). 🧮
Questions Fréquemment Posées
La leçon « Floyd-Warshall entre toutes les paires » est-elle gratuite ?
Oui — le texte complet de « Floyd-Warshall entre toutes les paires » est gratuit à lire ici sur le web. Pour la pratiquer de manière interactive (un éditeur de code intégré et un tuteur IA 24/7) et déverrouiller le reste du cours Competitive Programming Academy, passe à CoddyKit PRO. Le cours Competitive Programming Academy comprend 4 leçons au total.
Qu'est-ce que j'apprendrai dans « Floyd-Warshall entre toutes les paires » ?
Trouver les plus courts chemins entre chaque paire Tu pratiques Competitive Programming Academy avec du code pratique que tu exécutes directement dans le navigateur, et un tuteur IA 24/7 répond à tes questions au fur et à mesure que tu avances dans la leçon.
Dois-je avoir de l'expérience pour commencer Competitive Programming Academy ?
Aucune expérience préalable n'est requise. Competitive Programming Academy sur CoddyKit est structuré pour les débutants jusqu'aux apprenants avancés, donc tu peux commencer ici ou depuis le début et avancer à ton rythme. Ceci est la leçon 4 sur 4.
Combien de temps prend la leçon « Floyd-Warshall entre toutes les paires » ?
La plupart des leçons CoddyKit prennent environ 5–10 minutes. Chacune est courte et interactive, tu progresses régulièrement et tu repiques exactement où tu t'es arrêté sur le web et l'app.
Peux-tu écrire et exécuter du code dans cette leçon Competitive Programming Academy ?
Oui. Chaque leçon Competitive Programming Academy inclut un éditeur de code intégré, tu écris et exécutes du vrai code directement dans ton navigateur et tu reçois des retours IA instantanés — aucune configuration locale requise.
Toutes les leçons de ce cours
- Dijkstra avec un tas
- BFS 0-1 avec une deque
- Bellman-Ford et arêtes négatives
- Floyd-Warshall entre toutes les paires