Поиск потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости

Задача

Задача о потоке минимальной стоимости состоит в нахождении среди всех потоков данной величины наименее затратного.

Идея

В основе алгоритма лежит теорема Форда-Фалкерсона о потоке минимальной стоимости. На каждой итерации алгоритма будем находить путь минимальной стоимости из [math]s[/math] в [math]t[/math] и дополнять поток вдоль этого пути. Выбирать алгоритм для поиска кратчайших путей следует с учетом того, что в ходе алгоритма появляются ребра отрицательного веса.

Реализация

for [math]e \in E[/math] {
     [math]f[e] \leftarrow 0[/math]
}
while (существует путь [math]s \leadsto t[/math] в остаточной сети [math]G_f[/math]) {
      [math]P \leftarrow[/math] кратчайший в смысле стоимости путь [math]s \leadsto t[/math]
      дополнить поток [math]f[/math] вдоль [math]P[/math]
}

Корректность

Непосредственно следует из теоремы Форда-Фалкерсона о потоке минимальной стоимости.

Асимптотика

Каждая итерация выполняется за время работы поиска кратчайшего пути, обозначим его [math]F(V, E)[/math]. В сетях с целочисленной пропускной способностью итераций будет не более [math]|f|[/math].

Итого получаем время работы [math]O(F(V, E) \cdot |f|)[/math].

Литература

• Ravindra Ahuja, Thomas Magnanti, James Orlin. Network flows (1993)