Comments 8
Алгоритм пожалуй элегантный, но ассимптотическая сложность пугает. O((V**2)*E)) где E количество ребер, то есть может быть V!, в википедии подсмотрел)) А задача то из реального мира. Неужели не было придумано оптимизаций или эвристик?
Придумано, и много, но уже отнюдь не для начинающих Maximum flow problem - Wikipedia
Алгоритм Диница + capacity scaling даёт 
, U - максимальная пропускная способность.Вроде как есть варианты сделать 
. В любом случае интереснее кто быстрее номинально, а не асимптотически. Лет 10 назад когда плотно изучал вопрос хороши были как раз Диница и Preflow, последний как раз был хорош благодаря двум эвристикам (max height и global relabeling), благодаря которым становился очень быстр. У Эндрю Гольдберга в личной библиотеке были реализации обоих и вроде как они были сопоставимы по скорости. К сожалению эта библиотека скорее всего канула в лету. Префлоу я недавно видел в лимоне, в networkx реализованы оба, можно попробовать замерить, но учитывая что они там на питоне реализованы это будет очень условно. На алгоритм Бойкова-Колмогорова можно обратить внимание, он по асимптотике не очень, но вроде как зарекомендовал себя на практике для выделения границ в изображении.
P. S. @csharpminor0 алгоритм Диница не для начинающих ...
P. S. @csharpminor0 алгоритм Диница не для начинающих ...
Статья посвящена простой передачи сути алгоритма, словами типа "от старого дуба 10 шагов налево и ставишь ведро здесь" а не замерам сложности алгоритма и не сравнению сложности. Для начального решения задачи сложность не важна. Преждевременная оптимизация - самое зло. Но отпугивание начинающих словами "это покамест не для тебя..." - еще большее зло.
Интересный алгоритм. Получается, это взвешенный направленный (движение бывает односторонним, файрволлы разрешают передачу данных только в одну сторону и т.д.) граф с динамически изменяемыми весами рёбер во время выполнения задачи.
Алгоритм "поднять-в-начало" вообще имба
Алгоритм Диница: как найти максимальный поток в сети (для начинающих)