Поиск потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости
Версия от 06:24, 27 декабря 2011; Proshev (обсуждение | вклад)
Содержание
Идея
В основе алгоритма лежит теорема Форда-Фалкерсона о потоке минимальной стоимости. На каждой итерации алгоритма будем находить путь из в минимальной стоимости и дополнять поток вдоль этого пути.
Реализация
for{ } while (существует путь в остаточной сети ) { кратчайший в смысле стоимости путь дополнить поток вдоль }
Корректность
Непосредственно следует из теоремы Форда-Фалкерсона о потоке минимальной стоимости.
Асимптотика
Каждая итерация выполняется за время работы поиска кратчайшего пути, обозначим его
. В сетях с целочисленной пропускной способностью итераций будет не более .Итого получаем время работы
.