Algorithme de Ford-Fulkerson
- Introduite par
- Lester R. Ford and Delbert R. Fulkerson
- Année
- 1956
- Type
- algorithm
- Famille
- Graph Algorithms
Ce texte est une traduction automatique et n’a pas encore été relu. Lire l’original en anglais
À quoi sert-elle ?
L'algorithme de Ford-Fulkerson, développé par Lester R. Ford et Delbert R. Fulkerson en 1956, est une méthode fondamentale pour calculer le flux maximal dans un réseau de flot.
Il détermine la quantité maximale de flot pouvant être envoyée d'une source à un puits à travers un graphe orienté avec des contraintes de capacité sur les arêtes.
L’intuition derrière la méthode
L'algorithme fonctionne en trouvant de manière répétée des chemins augmentants de la source au puits à travers le réseau résiduel, où chaque arête a une capacité restante. Chaque chemin contribue un flot additionnel égal à sa capacité goulot (l'arête avec la capacité restante minimale sur le chemin). Le processus continue jusqu'à ce qu'il n'y ait plus de chemins augmentants, moment auquel le flot maximal est atteint. L'idée clé est le théorème flot-max coupe-min : le flot maximal est égal à la capacité de la coupe minimale dans le réseau.
Histoire
Ford et Fulkerson ont introduit le problème du flot maximal et leur algorithme séminal en 1956. Ce travail fut révolutionnaire, établissant à la fois une méthode algorithmique et le célèbre théorème flot-max coupe-min. Edmonds et Karp (1972) ont amélioré la complexité dans le pire des cas en utilisant la recherche en largeur d'abord pour la sélection des chemins. Des avancées ultérieures par Dinic, Karzanov et d'autres ont conduit à des algorithmes encore plus rapides, mais la méthode de Ford-Fulkerson reste un algorithme classique et pédagogiquement précieux en informatique.
Quand l’utiliser
Appliquer l'algorithme de Ford-Fulkerson pour trouver le flot maximal dans des réseaux de flot orientés ou non orientés avec des capacités entières positives. Il fonctionne bien pour les réseaux de petite à moyenne taille et offre une compréhension intuitive des concepts de flot de réseau. Pour les très grands réseaux ou lorsque des flots entiers sont requis, considérer les algorithmes d'Edmonds-Karp (utilisant BFS) ou de Dinic pour une meilleure performance dans le pire des cas. L'utiliser lorsque la compréhension du comportement de l'algorithme est aussi importante que la vitesse.
Limites et points d’attention
- La complexité temporelle dépend des valeurs de capacité (non polynomiale en général ; peut être exponentielle avec des capacités irrationnelles)
- Peut ne pas terminer si les capacités sont irrationnelles (nécessite une implémentation soignée avec une arithmétique rationnelle)
- Moins efficace que les algorithmes spécialisés comme Edmonds-Karp ou Dinic sur les grands réseaux
- Sensible à l'ordre de sélection des chemins augmentants
Les conditions de la source ne remplacent ni une revue scientifique indépendante ni la validation par un moteur d’analyse.
Points forts
- Approche simple et intuitive basée sur les chemins augmentants
- Solution optimale garantie lorsque les capacités sont rationnelles ou entières
- Efficace pour les réseaux avec de petites capacités entières
- Constitue le fondement théorique pour la compréhension de la dualité flot-max coupe-min
- Fonctionne avec des graphes orientés et non orientés
Applications
- Routage réseau : maximiser le débit de données de la source à la destination dans les réseaux de communication
- Réseaux de transport : déterminer la capacité de fret maximale entre les villes en tenant compte des contraintes routières et ferroviaires
- Appariement biparti : trouver des appariements maximaux dans les graphes bipartis en construisant des réseaux de flot
- Segmentation d'images : utiliser des algorithmes de flot maximal pour partitionner les images en premier plan et arrière-plan
- Planification des compagnies aériennes : optimiser le routage des avions pour maximiser le flux de passagers à travers les réseaux en étoile
- Analyse des protéines : calculer le flot maximal dans les réseaux biologiques pour comprendre les voies d'interaction
Comment ça marche
Comment ça marche
Initialiser le graphe résiduel avec des capacités égales aux capacités des arêtes originales et un flot nul sur toutes les arêtes.
Trouver un chemin augmentant de la source au puits dans le graphe résiduel en utilisant une recherche en profondeur ou en largeur, calculer la capacité minimale le long du chemin, et ajouter ce flot à toutes les arêtes du chemin tout en réduisant leurs capacités résiduelles.
Répéter l'augmentation jusqu'à ce qu'aucun chemin augmentant n'existe dans le graphe résiduel ; le flot total accumulé est le flot maximal.
Pièges courants
- Choisir de mauvais chemins augmentants qui entraînent une convergence lente ou des résultats incorrects
- Ne pas mettre à jour correctement les capacités résiduelles ou ne pas ajouter d'arêtes inverses pour annuler le flot
- Utiliser la division entière ou l'arithmétique à virgule flottante lorsque l'arithmétique exacte est requise pour la correction
Questions fréquentes
Qu'est-ce que le théorème flot-max coupe-min ?
Le théorème stipule que le flot maximal de la source au puits est égal à la capacité minimale de toute coupe séparant la source du puits. Cela fournit à la fois une compréhension théorique et une méthode de vérification pour les algorithmes de flot.
Pourquoi l'algorithme converge-t-il parfois lentement ?
Avec des sélections de chemins malheureuses, l'algorithme peut n'augmenter le flot que d'une unité par itération, même lorsque des augmentations plus importantes sont possibles. L'utilisation de la recherche en largeur d'abord (Edmonds-Karp) assure une convergence en temps polynomial.
Comment l'algorithme gère-t-il les arêtes non orientées ?
Remplacer chaque arête non orientée par deux arêtes orientées dans des directions opposées, toutes deux avec la même capacité. L'algorithme trouve alors le flot sur le réseau orienté.
Quelle est la différence entre le flot sur une arête et la capacité résiduelle ?
Le flot sur une arête représente la quantité de matière envoyée le long de celle-ci, tandis que la capacité résiduelle est la capacité restante disponible. La capacité résiduelle diminue à mesure que le flot augmente, et les arêtes inverses suivent la capacité d'annuler le flot.
Méthodes associées
Sources
Ford, L. R., & Fulkerson, D. R. (1956). Maximal flow through a network. Canadian Journal of Mathematics, 8(3), 399-404.
Ouvrir la référence DOICopié.Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press.
ISBN : 978-0-262-03384-8Copié.