Flot maximal et coupe minimale

Saisir des arêtes orientées entre S, A, B, C, D et T sous la forme S -> A 10 ; S est la source et T le puits. Point et virgule décimaux sont acceptés, avec six décimales au plus. Les capacités peuvent être nulles ; chaque paire orientée est limitée à 1000000 au total. Les lignes vides sont ignorées, les lignes parallèles additionnées. Un puits inaccessible donne un flot maximal nul. Les entrées, même les réseaux incomplets ou invalides, et le délai d’animation sont enregistrés localement. Recharger attend une action ; la progression du calcul n’est pas enregistrée. Le graphe utilise jusqu’à trois chiffres significatifs ; ≈ indique un arrondi. L’infobulle d’une arête et ses détails donnent la précision complète affichée. Masquer la page met l’animation en pause jusqu’à une reprise explicite.

Calculer donne immédiatement le flot maximal final. Étape poursuit le calcul d’un plus court chemin augmentant ; Animer continue le même calcul et Pause l’arrête. Recommencer efface le flot pour la saisie actuelle. Modifier la saisie arrête l’animation et retire les anciens résultats. L’exemple Arête inverse montre comment un chemin résiduel peut annuler un choix précédent.

Les arêtes affichent flot/capacité. L’orange indique le dernier chemin résiduel ; une arête pointillée est parcourue à rebours. À la fin, les arêtes rouges traversent la coupe minimale et les contours bleus indiquent le côté S. La partition donne le côté S avant la barre, le côté T après. La capacité de coupe égale le flot maximal. Les détails donnent les valeurs accessibles dans les deux sens résiduels. Avec des arêtes originales opposées, la capacité résiduelle combine capacité disponible en avant et flot opposé annulable ; les flots affichés utilisent une représentation admissible après annulation des flots opposés.

Edmonds–Karp utilise un parcours en largeur du graphe résiduel. Le dessin comporte six sommets fixes ; dans les réseaux denses les étiquettes peuvent se croiser, consulter alors le tableau. Les décimales utilisent les nombres flottants JavaScript et peuvent être arrondies sur les derniers chiffres. Princeton : flot maximal.