Поиск потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости
Содержание
Идея
В основе алгоритма лежит теорема Форда-Фалкерсона о потоке минимальной стоимости. На каждой итерации алгоритма будем находить путь из в минимальной стоимости и дополнять поток вдоль этого пути. Так как появляются ребра отрицательного веса. Выбирать алгоритм для поиска кратчайших путей следует с учетом этого факта.
Реализация
for{ } while (существует путь в остаточной сети ) { кратчайший в смысле стоимости путь дополнить поток вдоль }
Корректность
Непосредственно следует из теоремы Форда-Фалкерсона о потоке минимальной стоимости.
Асимптотика
Каждая итерация выполняется за время работы поиска кратчайшего пути, обозначим его
. В сетях с целочисленной пропускной способностью итераций будет не более .Итого получаем время работы
.Литература
- Ravindra Ahuja, Thomas Magnanti, James Orlin. Network flows (1993)