Algorithme de Floyd-Warshall

Plus courts chemins entre toutes les paires

Exercice Avancé · Graphes · prepa scientifique et economique (CPGE)

Enonce

Implémenter floyd_warshall(sommets, aretes) qui renvoie la matrice $n \times n$ des distances minimales entre toutes les paires de sommets.

Tester sur un petit graphe orienté avec 4 sommets et quelques arcs pondérés. Vérifier la cohérence avec un Dijkstra appliqué depuis chaque sommet.

Signature attendue

def floyd_warshall(sommets: list, aretes: list) -> list:

Exemple

floyd_warshall([0, 1, 2], [(0, 1, 3), (1, 2, 1), (2, 0, 2)]) → [[0, 3, 4], [3, 0, 1], [2, 5, 0]]

📖 Rappel de cours

L'algorithme de Floyd-Warshall calcule les plus courts chemins entre toutes les paires de sommets en une seule passe. Il fonctionne avec des poids quelconques (positifs ou négatifs), à condition qu'il n'y ait pas de cycle de poids strictement négatif.

Programmation dynamique :

Soit $D_k(i, j)$ = poids du plus court chemin de $i$ à $j$ utilisant uniquement les sommets intermédiaires $\{0, 1, \ldots, k\}$.

Récurrence :

$D_k(i, j) = \min\bigl(D_{k-1}(i, j),\ D_{k-1}(i, k) + D_{k-1}(k, j)\bigr)$

Soit on n'utilise pas $k$ (premier terme), soit on passe par $k$ (deuxième terme).

Initialisation :

$D(i, i) = 0$
$D(i, j) = w(i, j)$ s'il existe un arc $i \to j$ de poids $w$
$D(i, j) = +\infty$ sinon

L'astuce : on peut réutiliser le même tableau $D$ d'une étape à l'autre — l'ordre d'évaluation de la récurrence rend la mise à jour en place correcte.

← Exercices sur les graphes en Python — BFS, DFS, Dijkstra

Exercices du meme theme

La correction commentee, les indices progressifs, l'execution du code dans le navigateur et la verification par l'IA sont reserves aux abonnes.