147
правок
Изменения
→Алгоритм
На основании теоремы построим алгоритм.. На каждой итерации алгоритма будем находить путь минимальной стоимости из <tex>s</tex> в <tex>t</tex> в остаточной сети и дополнять поток вдоль него. Выбирать алгоритм для поиска кратчайших путей следует с учетом того, что в ходе алгоритма появляются ребра отрицательного веса.
===РеализацияОписание===
* Начало.
* '''Шаг 1'''. Для каждого ребра зададим поток равный <tex>0</tex>.
* '''Шаг 6'''. Поток минимальной стоимости найден, т.к в остаточной сети не осталось ни одного пути.
* Конец.
===Реализация===
'''for''' <tex>e \in E</tex> {
<tex>f[e] \leftarrow 0</tex>
}
'''while''' (существует путь <tex>s \leadsto t</tex> в остаточной сети <tex>G_f</tex>) {
<tex>P \leftarrow</tex> кратчайший в смысле стоимости путь <tex>s \leadsto t</tex>
дополнить поток <tex>f</tex> вдоль <tex>P</tex>
}
===Асимптотика===
