Максимальный поток в невзвешенном графике

Question

Проблема максимального потока обычно решается с помощью алгоритма Эдмонда-Карпа, который строит остаточный граф и использует BFS для поиска путей расширения.

Но обычно проблема максимального потока определяется для взвешенного графа. Для невзвешенного графа мы можем просто рассматривать вес каждого ребра как 1, но мне интересно, есть ли какой-нибудь более простой алгоритм для решения невзвешенной версии.

Answer 1

Обычно люди ссылаются на граничные «пропускные способности», когда говорят о проблемах с потоком, и «вес/стоимость», когда говорят о проблемах, связанных с расстоянием. Это вызывает меньше путаницы.

Перефразируя ваш вопрос, существует ли более простой алгоритм для задачи о максимальном потоке, когда каждое ребро имеет емкость 1?

Это действительно зависит от того, что вы подразумеваете под «проще», но вы можете использовать алгоритм Форда-Фалкерсона для решения этого особого случая в O(VE)с ограничением по времени, что намного быстрее, чем решение с помощью вышеупомянутого алгоритма Эдмондса-Карпа с ограничением по времени O(VE^2).