Как разорвать связь в кратчайшей длине увеличения в алгоритме Эдмондса-Карпа?
Итак, если 2 кратчайших пути дополнения имеют длину 2, что такое вторичный фильтр?
Из того, что я понимаю, Эдмондс-Карп выбирает кратчайший путь, то есть путь с наименьшим количеством ребер.
Однако оба эти пути имеют длину 2. Таким образом, этот алгоритм затем расширяется и говорит "выберите путь с максимальным / минимальным потоком"?
1 ответ
Решение
Неважно, какой путь выбран. Доказательства правильности и сложности еще проходят.