Calculateur de Flot Maximum

Pseudocode

Tous les algorithmes de flot maximal de cette famille sont la même boucle: trouver un chemin de la source au puits disposant de capacité libre, y pousser tout ce qu'il permet, recommencer. Ils ne diffèrent que par la manière de choisir ce chemin.

FlotMaximal(graphe, s, t):
    flot = 0
    construire le graphe residuel: cap(u,v) avant, 0 arriere

    tant qu il existe un chemin augmentant P de s a t
          dans le graphe residuel:
        goulot = capacite residuelle minimale le long de P
        pour chaque arete (u, v) de P:
            residuel[u][v] -= goulot
            residuel[v][u] += goulot   // arete d annulation
        flot += goulot

    renvoyer flot

// Ford-Fulkerson: trouve P par DFS (chemin quelconque)
// Edmonds-Karp:   trouve P par BFS (plus court chemin)

L'arête résiduelle arrière est la partie qui semble erronée et se révèle indispensable. Elle permet à un chemin augmentant ultérieur d'annuler du flot poussé plus tôt, si bien que l'algorithme se dégage d'un mauvais choix initial sans jamais revenir en arrière explicitement. Sans ces arêtes d'annulation, la boucle gloutonne se bloque sur un flot sous-optimal.

Exemple détaillé, étape par étape

Exécute Edmonds-Karp sur l'exemple classique où un premier choix glouton doit être défait par la suite.

Graphe d'exemple: Capacités orientées: S vers A (10), S vers B (10), A vers B (2), A vers T (4), B vers T (9).

1. Augmentation 1. Le BFS trouve S vers A vers T. Le goulot vaut min(10, 4) = 4. Pousse 4. Flot total 4. Le résiduel S-A descend à 6 et A-T à 0.
2. Augmentation 2. Le BFS trouve S vers B vers T. Le goulot vaut min(10, 9) = 9. Pousse 9. Flot total 13. Le résiduel S-B descend à 1 et B-T à 0.
3. Augmentation 3. A-T et B-T sont toutes deux saturées, il ne reste donc aucune route directe. Le BFS ne trouve plus de chemin augmentant: atteindre T exigerait A-T ou B-T, et les deux sont pleines.
4. Vérifier la coupe. Quelles arêtes sont saturées? A-T à 4 et B-T à 9, soit une capacité totale de 13. Les retirer déconnecte T de S, c'est donc une coupe de capacité 13, et le flot de 13 l'atteint exactement.
5. Pourquoi l'arête d annulation compte. Si le premier chemin augmentant avait été S vers A vers B vers T en poussant 2, l'arête A-B serait saturée d'une manière qui ne bloque rien ici. Mais dans les graphes où le chemin glouton accapare de la capacité dont un chemin ultérieur a besoin, l'arête résiduelle arrière B vers A permet de repousser ces 2 unités et de les réacheminer. L'algorithme n'a jamais à revenir en arrière explicitement.

Le flot maximal vaut 13, et la coupe minimale est la paire d'arêtes A-T et B-T de capacité totale 13. Que les deux nombres coïncident n'est pas un hasard: c'est le théorème flot-max coupe-min.

Complexité et son origine

Temps: O(V·E^2) avec Edmonds-Karp · Espace: O(V + E)

Ford-Fulkerson avec un choix de chemin arbitraire s'exécute en O(E fois le flot maximal), car chaque augmentation ajoute au moins une unité tandis que la recherche de chemin coûte O(E). C'est pseudo-polynomial et véritablement mauvais: avec des capacités de l'ordre du milliard, cela peut demander un milliard d'augmentations, et avec des capacités irrationnelles cela peut ne jamais terminer. Edmonds-Karp corrige ce défaut en choisissant toujours le plus court chemin augmentant par BFS. La distance de la source au puits ne décroît jamais, et chaque arête ne peut être le goulot que V/2 fois au plus, ce qui borne le nombre d'augmentations à O(VE) et le total à O(V fois E au carré). Dinic regroupe les augmentations en phases à l'aide d'un graphe de niveaux et améliore cela en O(V au carré fois E), ou O(E fois racine de V) sur les graphes à capacités unitaires.

Quand utiliser Flot Maximum, et quand l'éviter

Le choix dépend surtout de l'ordre de grandeur des capacités et de la taille du graphe.

Pièges fréquents

• Omettre les arêtes résiduelles arrière. Sans elles, l'algorithme ne peut défaire une mauvaise augmentation antérieure et s'arrête sur un flot seulement maximal au sens de non extensible, pas maximal en valeur. C'est le bogue de flot maximal le plus courant et il produit des réponses plausibles mais trop petites.
• Choisir le chemin par DFS avec de grandes capacités. Ford-Fulkerson pur avec DFS peut nécessiter une augmentation par unité de flot sur des graphes défavorables. L'exemple classique, avec des capacités d'un million et une arête goulot de un, demande un million d'itérations. Le BFS rend ce nombre indépendant des valeurs de capacité.
• Oublier que la conservation du flot exclut source et puits. Tout autre sommet doit avoir un flot entrant égal au flot sortant. Vérifier la conservation à la source ou au puits échouera toujours et constitue une source de confusion fréquente lors de l'écriture des tests.
• Supposer que le flot maximal est unique. La valeur du flot maximal est unique; l'affectation qui l'atteint ne l'est généralement pas, ni la coupe minimale lorsque plusieurs partagent la même capacité. Les tests doivent vérifier la valeur, pas une affectation arête par arête.
• Modéliser des capacités de sommets comme des capacités d arêtes. Si un sommet possède sa propre limite de débit, il faut le scinder en un sommet d'entrée et un sommet de sortie reliés par une arête de cette capacité. Appliquer la limite aux arêtes incidentes pose un problème différent et faux.

Questions fréquentes

Quel est le problème du flot maximal?

Étant donné un graphe orienté où chaque arête possède une capacité, ainsi qu'une source et un puits, le flot maximal demande le débit le plus élevé auquel de la matière peut circuler de la source au puits sans dépasser aucune capacité et en conservant le flot à chaque sommet intermédiaire. Il modélise le débit dans les canalisations, les réseaux, la logistique et l'ordonnancement.

Que dit le théorème flot-max coupe-min?

La valeur du flot maximal de la source au puits égale toujours la capacité de la coupe minimale qui les sépare. Intuitivement, le flot ne peut dépasser aucune coupe puisque tout doit la traverser, et lorsqu'il ne reste aucun chemin augmentant, les sommets atteignables dans le graphe résiduel définissent une coupe dont la capacité correspond exactement au flot.

Quelle est la différence entre Ford-Fulkerson et Edmonds-Karp?

C'est la même méthode des chemins augmentants avec un choix de chemin différent. Ford-Fulkerson laisse ce choix non spécifié, typiquement un DFS, ce qui fait dépendre le temps d'exécution des valeurs de capacité et peut être catastrophiquement lent. Edmonds-Karp prend toujours le plus court chemin augmentant par BFS, ce qui borne le travail à O(V fois E au carré) quelles que soient les capacités.

Pourquoi les algorithmes de flot maximal ont-ils besoin d arêtes résiduelles?

Parce que l'algorithme est glouton et ne peut anticiper. Une arête résiduelle arrière représente la possibilité d'annuler du flot déjà poussé le long de cette arête, si bien qu'un chemin augmentant ultérieur peut réacheminer des décisions antérieures. C'est ce qui permet à une boucle purement progressive d'atteindre un véritable optimum sans retour en arrière.

Quelle est la complexité temporelle du flot maximal?

Edmonds-Karp s'exécute en O(V fois E au carré). Dinic l'améliore en O(V au carré fois E), et en O(E fois la racine carrée de V) sur les graphes à capacités unitaires, ce qui explique sa préférence pour le couplage biparti. Ford-Fulkerson pur est en O(E fois la valeur du flot maximal), donc pseudo-polynomial plutôt que polynomial.