15
правок
Изменения
Нет описания правки
==Идея==
В основе алгоритма лежит [[Теорема Форда-Фалкерсона о потоке минимальной стоимости|теорема Форда-Фалкерсона о потоке минимальной стоимости]]. На каждой итерации алгоритма будем находить путь из <tex>s</tex> в <tex>t</tex> минимальной стоимости и дополнять поток вдоль этого пути.
==Реализация==
'''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>
}
==Корректность==
Непосредственно следует из [[Теорема Форда-Фалкерсона о потоке минимальной стоимости|теоремы Форда-Фалкерсона о потоке минимальной стоимости]].
==Асимптотика==
Каждая итерация выполняется за время работы поиска кратчайшего пути, обозначим его <tex>F(V, E)</tex>. В сетях с целочисленной пропускной способностью итераций будет не более <tex>|f|</tex>.
Итого получаем время работы <tex>O(F(V, E) \cdot |f|)</tex>.
В основе алгоритма лежит [[Теорема Форда-Фалкерсона о потоке минимальной стоимости|теорема Форда-Фалкерсона о потоке минимальной стоимости]]. На каждой итерации алгоритма будем находить путь из <tex>s</tex> в <tex>t</tex> минимальной стоимости и дополнять поток вдоль этого пути.
==Реализация==
'''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>
}
==Корректность==
Непосредственно следует из [[Теорема Форда-Фалкерсона о потоке минимальной стоимости|теоремы Форда-Фалкерсона о потоке минимальной стоимости]].
==Асимптотика==
Каждая итерация выполняется за время работы поиска кратчайшего пути, обозначим его <tex>F(V, E)</tex>. В сетях с целочисленной пропускной способностью итераций будет не более <tex>|f|</tex>.
Итого получаем время работы <tex>O(F(V, E) \cdot |f|)</tex>.
