Qu'est-ce que le problème du flux maximal ?

Il demande le plus grand flux total pouvant être acheminé d'un nœud source désigné à un nœud puits désigné à travers un réseau d'arêtes orientées, chacune limitée par une capacité.

Comment fonctionne l'algorithme d'Edmonds-Karp ?

Il utilise à plusieurs reprises la recherche en largeur pour trouver le chemin augmentant disponible le plus court de la source au puits dans le graphe résiduel, pousse le flux maximal possible le long de ce chemin (limité par sa plus petite capacité restante), et répète jusqu'à ce qu'il ne reste plus de chemin.

Qu'est-ce qu'un graphe résiduel ?

C'est un graphe qui suit combien de flux supplémentaire peut encore être poussé le long de chaque arête (capacité restante) plus une arête 'inverse' pour le flux déjà envoyé, ce qui permet à l'algorithme d'effectivement 'annuler' un choix antérieur sous-optimal.

Qu'est-ce que le théorème du flux maximal-coupe minimale ?

Il stipule que le flux maximal de la source au puits est toujours exactement égal à la capacité totale minimale de toute 'coupe' (ensemble d'arêtes qui, si retirées, déconnecteraient la source du puits) — une garantie fondamentale expliquant pourquoi Edmonds-Karp trouve le véritable optimum.

Pourquoi utiliser BFS plutôt qu'un chemin quelconque (Ford-Fulkerson) ?

Le Ford-Fulkerson simple peut choisir des chemins augmentants arbitrairement mauvais et s'exécuter lentement sur certains graphes ; toujours choisir le chemin le plus court via BFS (Edmonds-Karp) garantit que l'algorithme se termine en temps polynomial, O(VE²).

Que signifie la flèche '->' dans la saisie d'arêtes ?

Elle indique une arête orientée — A->B:10 signifie que jusqu'à 10 unités de flux peuvent se déplacer de A vers B, mais pas de B vers A (sauf si une arête séparée B->A est également saisie).

Combien de nœuds ce calculateur peut-il gérer ?

Ce calculateur prend en charge jusqu'à 30 nœuds, gardant le calcul d'Edmonds-Karp instantané tout en couvrant la grande majorité des exemples de réseaux saisis manuellement.

Où le flux maximal est-il utilisé dans la vie réelle ?

Il modélise l'allocation de bande passante réseau, le routage du trafic et des transports, l'appariement biparti (attribution d'emplois, applications de rencontres), la distribution de pipelines d'eau/pétrole et la segmentation d'images en vision par ordinateur.

Calculateur de Flux Réseau — Trouvez le Flux Maximal à Travers un Réseau

Notre Calculateur de Flux Réseau trouve la quantité maximale de flux pouvant être poussée d'un nœud source à un nœud puits à travers un graphe orienté où chaque arête a une capacité limitée, à l'aide de l'algorithme d'Edmonds-Karp (Ford-Fulkerson basé sur BFS), votre réseau étant saisi comme une simple liste d'arêtes textuelle (ex. A->B:10, B->C:5).

Réponse rapide

Saisissez votre graphe orienté à capacités et une paire source/puits pour trouver instantanément le flux maximal via l'algorithme d'Edmonds-Karp.

Arêtes orientées (séparées par des virgules)

Saisissez des arêtes sous la forme NœudA->NœudB:capacité, par ex. A->B:10, B->C:5.

Source

Puits

Comment utiliser Calculateur de Flux Réseau — Flux Maximal via Edmonds-Karp en Ligne

1
Saisissez votre graphe orienté à capacités comme une liste d'arêtes séparées par des virgules, ex. A->B:10, B->C:5.
2
Saisissez les noms des nœuds source et puits.
3
Cliquez sur 'Calculer' pour trouver le flux maximal via Edmonds-Karp.

Pourquoi utiliser Calculateur de Flux Réseau — Flux Maximal via Edmonds-Karp en Ligne ?

Le flux maximal demande combien de quantité totale ('choses' comme des données, de l'eau, du trafic) peut se déplacer d'une source à un puits à travers un réseau où chaque arête a une capacité limitée. L'algorithme d'Edmonds-Karp résout cela exactement : il trouve à plusieurs reprises tout chemin augmentant le plus court de la source au puits à l'aide de BFS dans le graphe résiduel (le graphe de capacité restante, incluant des arêtes 'd'annulation' pour le flux déjà envoyé), pousse le flux maximal possible le long de ce chemin, et répète jusqu'à ce qu'il ne reste plus de chemin augmentant — moment auquel le flux total poussé est égal au flux maximal possible, un fait garanti par le théorème du flux maximal-coupe minimale.

Questions fréquentes

Outils similaires

Calculatrice du Plus Court Chemin de Dijkstra — Graphes Pondérés en Ligne

Trouvez le plus court chemin et la distance totale entre deux nœuds dans un graphe pondéré à l'aide de l'algorithme de Dijkstra. Calculatrice gratuite avec une simple saisie de liste d'arêtes.

Calculatrice d'Arbre Couvrant Minimal — Algorithme de Kruskal en Ligne

Trouvez l'arbre couvrant minimal d'un graphe pondéré à l'aide de l'algorithme de Kruskal. Calculatrice gratuite avec une simple saisie de liste d'arêtes et détection de cycles par union-find.

Solveur de Programmation Linéaire — Méthode des Points d'Angle à 2 Variables en Ligne

Résolvez un programme linéaire à 2 variables en trouvant et en évaluant chaque point d'angle de la région réalisable. Calculateur gratuit, maximisez ou minimisez avec des contraintes linéaires.