37
правок
Изменения
Нет описания правки
return Cmin
u.vis <- true
for (uv \in E)
if (!v.vis) && (uv.f < uv.c)
дельта <- dfs(v, min(Cmin, uv.c - uv.f))
if (дельта > 0) {
uv.f += дельта
uv.rbackEdge.f -= дельта
return дельта
}
}
== Оценка производительности ==
Добавляя поток увеличивающего пути к уже имеющемуся потоку, максимальный поток будет получен, когда нельзя будет найти увеличивающий путь. Тем не менее, если величина пропускной способности — иррациональное число, то алгоритм может работать бесконечно. В целых числах таких проблем не возникает и время работы ограничено <tex>O(E*f)</tex>, где <tex>E</tex> — число рёбер в графе, <tex>f</tex> — максимальный поток в графе, так как каждый увеличивающий путь может быть найден за <tex>O(E)</tex> и увеличивает поток как минимум на 1.
=== Пример несходящегося алгоритма ===
Рассмотрим приведённую справа сеть, с источником <math>\ s</math>, стоком <math>\ t</math>, пропускными способностями рёбер <math>\ e_1</math>, <math>\ e_2</math> и <math>\ e_3</math> соответственно <math>\ 1</math>, <math>r=(\sqrt{5}-1)/2</math> и <math>\ 1</math> и пропускной способностью всех остальных рёбер, равной целому числу <math>M \ge 2</math>. Константа <math>\ r</math> выбрана так, что <math>\ r^2 = 1 - r</math>. Мы используем пути из остаточного графа, приведённые в таблице, причём <math>\ p_1 = \{ s, v_4, v_3, v_2, v_1, t \}</math>, <math>\ p_2 = \{ s, v_2, v_3, v_4, t \}</math> и <math>\ p_3 = \{ s, v_1, v_2, v_3, t \}</math>.
{| class="wikitable" style="text-align: center"
! rowspan=2 | Шаг !! rowspan=2 | Найденный путь !! rowspan=2 | Добавленный поток !! colspan=3 | Остаточные пропускные способности
|-
! <math>e_1</math> !! <math>e_2</math> !! <math>e_3</math>
|-
| 0 || || || <math>r^0=1</math> || <math>r</math> || <math>1</math>
|-
| 1 || <math>\{ s, v_2, v_3, t \}</math> || <math>1</math> || <math>r^0</math> || <math>r^1</math> || <math>0</math>
|-
| 2 || <math>p_1</math> || <math>r^1</math> || <math>r^2</math> || <math>0</math> || <math>r^1</math>
|-
| 3 || <math>p_2</math> || <math>r^1</math> || <math>r^2</math> || <math>r^1</math> || <math>0</math>
|-
| 4 || <math>p_1</math> || <math>r^2</math> || <math>0</math> || <math>r^3</math> || <math>r^2</math>
|-
| 5 || <math>p_3</math> || <math>r^2</math> || <math>r^2</math> || <math>r^3</math> || <math>0</math>
|}
Заметим, что после шага 1, как и после шага 5, остаточные способности рёбер <math>e_1</math>, <math>e_2</math> и <math>e_3</math> имеют форму <math>r^n</math>, <math>r^{n+1}</math> and <math>0</math>, соответственно, для какого-то натурального <math>n</math>. Это значит, что мы можем использовать увеличивающие пути <math>p_1</math>, <math>p_2</math>, <math>p_1</math> и <math>p_3</math> бесконечно много раз, и остаточные пропускные способности этих рёбер всегда будут в той же форме.Полный поток после шага 5 равен <math>1 + 2(r^1 + r^2)</math>. За бесконечное время полный поток сойдётся к <math>\textstyle 1 + 2\sum_{i=1}^\infty r^i = 3 + 2r</math>, тогда как максимальный поток равен <math>2M + 1</math>. Таким образом, алгоритм не только работает бесконечно долго, но даже и не сходится к оптимальному решению.<ref>{{cite journal| title = The smallest networks on which the Ford-Fulkerson maximum flow procedure may fail to terminate | first = Uri | last = Zwick | journal = [[Theoretical Computer Science (journal)|Theoretical Computer Science]] | volume = 148 | issue = 1 | date = 21 August 1995 | pages = 165–170 | doi = 10.1016/0304-3975(95)00022-O}}</ref>
=== Пример медленной работы алгоритма Форда-Фалкерсона с использованием поиска в глубину по сравнению с реализацией, использующей поиск в ширину ===
== См. также ==
* [[Теорема Форда-Фалкерсона]]
