Algorithme d Edmonds-Karp calcule le flot maximum en Python
Saisissez un graphe orienté capacitaire, choisissez la source et le puits, puis calculez automatiquement le flot maximum avec Edmonds-Karp. Le module affiche la valeur du flot, les chemins augmentants, une coupe minimale et un graphique de progression.
Résultats
Prêt pour le calcul
Le calculateur attend votre graphe. Utilisez l exemple fourni ou saisissez votre propre réseau capacitaire.
Guide expert : comprendre et implémenter l algorithme d Edmonds-Karp pour calculer le flot maximum en Python
L algorithme d Edmonds-Karp est l une des méthodes les plus pédagogiques et les plus robustes pour résoudre le problème du flot maximum dans un graphe orienté avec capacités. Si vous cherchez comment faire un algorithme d Edmonds-Karp calcule le flot maximum en Python, vous êtes au bon endroit : cette page combine un calculateur pratique, une explication algorithmique complète et une logique d implémentation claire. Le problème du flot maximum consiste à déterminer la quantité maximale qu une source peut envoyer vers un puits dans un réseau, sans dépasser les capacités des arêtes.
Cette famille de problèmes est centrale en informatique théorique, en optimisation combinatoire et dans de nombreux cas industriels. Elle apparaît dans la planification logistique, les réseaux de télécommunication, la circulation de paquets, la segmentation d images, le matching biparti et la distribution d énergie. Edmonds-Karp n est pas l algorithme le plus rapide dans l absolu, mais c est souvent le meilleur point de départ parce qu il formalise très bien les notions de graphe résiduel, de chemin augmentant et de borne de complexité.
Le principe de base du flot maximum
Dans un réseau de flot, chaque arête orientée (u, v) possède une capacité c(u, v) qui indique la quantité maximale que l on peut faire passer de u vers v. Un flot valide doit respecter trois contraintes :
- Capacité : le flot sur une arête ne peut jamais dépasser sa capacité.
- Conservation : pour tout sommet intermédiaire, ce qui entre doit égaler ce qui sort.
- Orientation : le flot se propage selon les arcs du graphe.
Le but est de maximiser la quantité totale envoyée depuis la source s vers le puits t. L idée de Ford-Fulkerson, dont Edmonds-Karp est une variante déterministe, est d améliorer progressivement une solution en recherchant un chemin augmentant dans le graphe résiduel. Ce graphe résiduel indique la capacité encore disponible sur chaque arête et inclut aussi des arêtes inverses qui permettent de corriger des choix précédents.
Qu apporte exactement Edmonds-Karp ?
La différence clé entre Ford-Fulkerson générique et Edmonds-Karp est la manière de choisir les chemins augmentants. Au lieu de prendre n importe quel chemin, Edmonds-Karp sélectionne systématiquement un chemin ayant le plus petit nombre d arêtes entre la source et le puits. Pour cela, il utilise une recherche en largeur, ou BFS. Cette stratégie n améliore pas toujours les performances pratiques sur les très gros graphes, mais elle garantit une complexité polynomiale en O(VE²), ce qui en fait un excellent compromis entre clarté et rigueur.
Concrètement, à chaque itération, on procède ainsi :
- Construire ou mettre à jour le graphe résiduel.
- Lancer une BFS depuis la source jusqu au puits.
- Si aucun chemin n existe, le flot actuel est maximal.
- Sinon, calculer le bottleneck, c est à dire la capacité minimale le long du chemin.
- Augmenter le flot de cette quantité et ajuster les capacités résiduelles.
C est précisément ce que fait le calculateur ci dessus. Lorsque vous cliquez sur le bouton, le script lit vos arêtes, construit la matrice de capacités, exécute Edmonds-Karp et affiche la suite des augmentations. Le graphique compare la valeur injectée à chaque itération avec le flot cumulé. Cette visualisation permet de voir comment le réseau se sature progressivement.
Pourquoi Python est un bon choix pour Edmonds-Karp
Python est particulièrement adapté à l apprentissage et au prototypage d algorithmes de graphes. Sa syntaxe réduit la charge cognitive, ce qui vous permet de vous concentrer sur la logique mathématique. Pour Edmonds-Karp, il est courant d utiliser soit :
- une matrice de capacités, simple et directe pour les petits graphes,
- une liste d adjacence, plus économique quand le graphe est clairsemé.
Dans un cadre pédagogique ou pour un calculateur de démonstration, la matrice est souvent le meilleur choix, car elle rend très explicite la mise à jour du résiduel. En revanche, sur des graphes plus grands, une liste d adjacence avec structures résiduelles explicites devient plus efficace. Si vous préparez un entretien technique ou un projet universitaire, savoir coder les deux approches est un avantage concret.
| Algorithme | Principe | Complexité théorique | Lecture pédagogique |
|---|---|---|---|
| Ford-Fulkerson | Chemins augmentants choisis librement | O(E × valeur du flot) si capacités entières | Simple à comprendre, mais dépend du choix des chemins |
| Edmonds-Karp | BFS sur le graphe résiduel | O(VE²) | Très bon équilibre entre rigueur, clarté et implémentation |
| Dinic | Graphe de niveaux et blocages | O(V²E) en borne générale | Souvent plus rapide en pratique sur de gros réseaux |
| Push-Relabel | Préflot et relabel local | O(V³) en version standard | Très performant dans de nombreux solveurs industriels |
Exemple classique : le réseau CLRS
L un des réseaux les plus connus en cours d algorithmique comporte 6 sommets et 10 arêtes. En appliquant Edmonds-Karp, on obtient un flot maximum de 23. Cette instance est très utilisée parce qu elle montre bien l intérêt des arêtes inverses résiduelles. Une première intuition naïve peut conduire à saturer certaines voies trop tôt, puis le résiduel permet de réacheminer une partie du flot afin d atteindre la solution optimale. C est un excellent cas pour vérifier votre code Python.
Voici une version compacte de l algorithme en Python. Elle suit exactement les étapes du calculateur, avec une matrice de capacités et une BFS qui mémorise les parents :
from collections import deque
def bfs(residual, s, t, parent):
n = len(residual)
for i in range(n):
parent[i] = -1
parent[s] = -2
q = deque([(s, float("inf"))])
while q:
u, flow = q.popleft()
for v in range(n):
if parent[v] == -1 and residual[u][v] > 0:
parent[v] = u
new_flow = min(flow, residual[u][v])
if v == t:
return new_flow
q.append((v, new_flow))
return 0
def edmonds_karp(capacity, s, t):
n = len(capacity)
residual = [row[:] for row in capacity]
parent = [-1] * n
max_flow = 0
while True:
path_flow = bfs(residual, s, t, parent)
if path_flow == 0:
break
max_flow += path_flow
v = t
while v != s:
u = parent[v]
residual[u][v] -= path_flow
residual[v][u] += path_flow
v = u
return max_flow
Cette implémentation est volontairement lisible. Dans une version de production, vous pouvez optimiser la structure de données, journaliser les chemins trouvés, calculer la coupe minimale ou convertir le résultat en affectation dans un problème de matching.
Comment interpréter les résultats du calculateur
Après calcul, vous obtenez plusieurs informations utiles :
- Flot maximum : la quantité totale maximale qui peut passer de la source au puits.
- Nombre d augmentations : le nombre de chemins trouvés par BFS avant saturation complète.
- Chemins augmentants : la séquence exacte des corrections successives.
- Coupe minimale : les arêtes qui séparent les sommets encore atteignables dans le résiduel de ceux qui ne le sont plus.
Le théorème max-flow min-cut garantit que la valeur du flot maximum est égale à la capacité de la coupe minimale. C est un résultat fondamental, car il relie une procédure constructive, l augmentation du flot, à une structure globale, la meilleure séparation du graphe. Si vous obtenez des résultats incohérents, la première chose à vérifier est souvent la gestion des arêtes inverses dans le résiduel.
| Instance de référence | Sommets | Arêtes | Flot maximum observé | Intérêt pédagogique |
|---|---|---|---|---|
| Réseau classique CLRS | 6 | 10 | 23 | Montre très bien les chemins augmentants et les retours résiduels |
| Petit réseau didactique | 4 | 5 | 5 | Idéal pour vérifier manuellement chaque itération |
| Matching biparti transformé | 8 | 12 | 4 | Illustre la réduction d un problème de matching au flot maximum |
Erreurs fréquentes lors du codage en Python
Plusieurs erreurs reviennent souvent lorsque l on implémente Edmonds-Karp en Python :
- Oublier les arêtes inverses résiduelles. Sans elles, l algorithme ne peut pas corriger une décision précédente.
- Écraser la capacité au lieu d additionner. Si plusieurs arêtes parallèles existent entre les mêmes sommets, il faut agréger correctement leurs capacités.
- Mal réinitialiser le tableau des parents. Chaque BFS doit repartir d un état propre.
- Confondre graphe original et graphe résiduel. Le flot final se déduit du résiduel, mais ce n est pas le résiduel lui même.
- Choisir une structure trop coûteuse. Une matrice simple peut être parfaite pour de petits n, mais devient lourde quand le graphe grossit.
Une autre difficulté courante est la visualisation. Beaucoup de développeurs savent calculer la valeur finale mais n inspectent pas les étapes intermédiaires. Or, afficher les augmentations successives permet de déboguer très vite un problème de BFS ou de mise à jour des capacités. C est pour cette raison que cette page inclut un graphique et le détail des chemins.
Applications concrètes d Edmonds-Karp
Même si des algorithmes plus avancés existent, Edmonds-Karp reste très utile dans des situations réelles de taille modérée et dans des workflows analytiques :
- Transport et supply chain : quantité maximale expédiable d entrepôts vers centres de distribution.
- Réseaux : débit maximal entre deux nœuds sous contraintes de lien.
- Matching : affectation de tâches, créneaux ou candidats via réduction en flot.
- Vision par ordinateur : base conceptuelle de certains modèles de coupe de graphe.
- Planification : vérification de faisabilité et identification des goulets d étranglement.
Le plus important est de comprendre que le résultat ne donne pas seulement une quantité maximale. Il révèle aussi où se situe la contrainte structurelle du réseau. Cette information est souvent plus précieuse encore que la valeur du flot, car elle vous indique quelles arêtes renforcer pour améliorer le système.
Quand Edmonds-Karp est-il le bon choix ?
Choisissez Edmonds-Karp si vous êtes dans l un de ces cas :
- vous apprenez les algorithmes de graphes et vous voulez une base solide ;
- vous implémentez un prototype Python lisible et testable ;
- la taille du graphe reste raisonnable ;
- vous avez besoin d expliquer ou de tracer chaque étape du calcul.
En revanche, pour des milliers ou millions d arêtes, il peut être préférable de passer à Dinic, Push-Relabel ou à une bibliothèque optimisée en C, C++ ou Rust avec interface Python. Toutefois, même dans ce cas, Edmonds-Karp reste souvent l outil de validation le plus clair pour créer des jeux de tests et comparer les sorties.
Ressources académiques et institutionnelles recommandées
Pour approfondir le sujet avec des sources solides, consultez ces références de qualité :
- Princeton University – Maxflow and Mincut
- MIT OpenCourseWare – Advanced Algorithms
- MIT CSAIL – Notes on Flow Computation
Conclusion
Si votre objectif est de comprendre comment un algorithme d Edmonds-Karp calcule le flot maximum en Python, retenez cette idée centrale : on part d un flot nul, on cherche itérativement un chemin augmentant par BFS dans le graphe résiduel, on pousse le maximum possible sur ce chemin, puis on recommence jusqu à blocage complet. Le résultat final est correct, traçable et théoriquement bien encadré.
Le calculateur de cette page vous permet de passer immédiatement de la théorie à la pratique. Modifiez le nombre de sommets, saisissez vos propres arêtes, comparez les itérations et observez la coupe minimale. C est une excellente façon de maîtriser l algorithme, de valider votre code Python et de mieux comprendre la structure cachée d un réseau capacitaire.