Algorithme de Floyd-Warshall
Les plus courts chemins entre toutes les paires de sommets : matrice des distances, étape k, formule de mise à jour, ordre des boucles, matrice des successeurs, coût en O(n³) et choix de l'algorithme de plus court chemin adapté.
- 25 cartes
- 6 thèmes
- Gratuit
Le programme, thème par thème
Le poids de chaque thème suit celui que lui donne l'examen.
- Notions
- Questions
- Ranger et relier
- Les chiffres
- Mises en situation
- Comprendre
Quelques cartes du deck
Sommet intermédiaire : de quoi s'agit-il ?
Voir la réponse
Sommet qu'un chemin traverse entre son départ et son arrivée ; l'étape k de l'algorithme autorise le sommet k à jouer ce rôle.
Après l'étape k, d[i][j] est la plus courte longueur d'un chemin de i à j dont les intermédiaires sont tous parmi les sommets 1 à k. À l'étape n, tous les sommets sont autorisés.
Les arcs sont 0 → 3, 3 → 2 et 2 → 1, chacun de poids 1. Le code place la boucle sur k à l'intérieur. Qu'affiche-t-il pour la ligne 0 ?
```python
INF = float("inf")
d = [[0, INF, INF, 1], [INF, 0, INF, INF], [INF, 1, 0, INF], [INF, INF, 1, 0]]
n = 4
for i in range(n):
for j in range(n):
for k in range(n):
d[i][j] = min(d[i][j], d[i][k] + d[k][j])
print(d[0])`[0, inf, 2, 1][0, 3, 2, 1][0, inf, inf, 1][0, 3, inf, 1]
Voir la réponse
[0, inf, 2, 1]Pour d[0][1], il faut le chemin 0, 3, 2, 1, trouvé avec 3 puis 2 comme intermédiaires : mais d[0][2] n'est calculé qu'après d[0][1], qui reste à inf. La bonne ligne,
[0, 3, 2, 1], demande k à l'extérieur : chaque étape est alors complète pour toutes les cases avant la suivante.À l'étape k de Floyd-Warshall, on pose d[i][j] = …(d[i][j], d[i][k] … d[k][j]) pour chaque couple (i, j).
Voir la réponse
À l'étape k de Floyd-Warshall, on pose d[i][j] = min(d[i][j], d[i][k] + d[k][j]) pour chaque couple (i, j).
On compare le meilleur chemin connu avec celui qui passe par k : de i à k, puis de k à j. Pour la fermeture transitive de Warshall, min et + deviennent ou et et.
Matrice des distances : de quoi s'agit-il ?
Voir la réponse
Tableau carré dont la case (i, j) contient la longueur du meilleur chemin connu du sommet i au sommet j : 0 sur la diagonale, l'infini quand aucun chemin n'est connu.
Au départ, elle contient les poids des arcs. Floyd-Warshall la remplit en n étapes ; elle ne garde que des longueurs, et les chemins se relisent avec la matrice des successeurs.