Flot Maximal — Edmonds-Karp
BFS dans le graphe résiduel
Enonce
Implémenter Edmonds-Karp sur une matrice de capacités C[u][v]. Retourner le flot maximal de source à puits.
⚠ Astuce : Travailler sur une copie R de C et y maintenir les capacités résiduelles. Toute augmentation $\delta$ sur l'arc $(u,v)$ retire $\delta$ à $R[u][v]$ et ajoute $\delta$ à $R[v][u]$.
Signature attendue
def edmonds_karp(C: list, source: int, puits: int) -> int:Exemple
edmonds_karp([[0, 3, 2, 0], [0, 0, 1, 2], [0, 0, 0, 3], [0, 0, 0, 0]], 0, 3)→5
📖 Rappel de cours
Dans un graphe orienté valué par des capacités $c(u,v)\geq 0$, un flot $f$ vérifie $f(u,v)\leq c(u,v)$ et la conservation aux nœuds intermédiaires. Le flot maximal est la valeur maximale de $\sum_v f(s,v)$.
Edmonds-Karp = Ford-Fulkerson + BFS :
Tant qu'il existe un chemin augmentant $s\to t$ dans le graphe résiduel (trouvé par BFS), augmenter le flot le long de ce chemin du minimum des capacités résiduelles.
$\text{complexité : } O(|V|\cdot|E|^2)$
Le choix du plus court chemin augmentant (BFS) borne le nombre d'augmentations.
← Exercices sur les graphes en Python — BFS, DFS, Dijkstra
Exercices du meme theme
- Algorithme de Floyd-Warshall
- Composantes Fortement Connexes (Kosaraju)
- Algorithme A* sur Grille
- Critère de Delaunay (in-circle)
La correction commentee, les indices progressifs, l'execution du code dans le navigateur et la verification par l'IA sont reserves aux abonnes.