Overview
Floyd-Warshall calcule les plus courts chemins entre toutes les paires de nœuds d'un graphe pondéré.
Analogy
Comme construire une table de distances entre toutes les villes d'une carte, en trouvant si passer par une ville intermédiaire est plus rapide.
Step-by-step
- Initialise dist[i][j] = poids de l'arête ou ∞
- Pour chaque nœud intermédiaire k
- Pour toutes les paires (i,j), vérifie si passer par k est plus court
- dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
Visual
dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j])
pour chaque k de 0 à V-1
Common mistakes
- Oublier d'initialiser dist[i][i] = 0
- Mauvais ordre des boucles (k doit être la boucle externe)
Practice questions
- Calcule toutes les distances de paires dans un petit graphe
- Détecte les cycles négatifs : si dist[i][i] < 0