Форд Фулкерсон из Cormen и др.

Я изучаю алгоритм Форда-Фулкерсона из Cormen "Введение в алгоритмы 2-го издания". Он описывается в псевдокоде для ориентированного графа G = (V, E) следующим образом, где f - поток, определенный на VxV

FORD-FULKERSON(G, s, t)
    for each edge (u,v) in E(G)
        do f[u, v] = 0
           f[v, u] = 0
    while there is a path p from s to t in the residual network Gf
        do m = min{c(u, v)-f[u, v]: (u, v) is on p}
            for each edge (u, v) on p
                do f[u, v] = f[u, v] + m
                   f[v, u] = - f[u, v]

Остаточный граф Gf имеет те же вершины, что и G, и имеет в качестве ребер эти упорядоченные пары вершины (u, v), для которых c (u, v) - f (u, v) > 0. (Edit: c - функция пропускной способности, заданная при запуске и расширенная на нуль на ребрах, не являющихся частью графика)

Я не уверен, что делать в случае, когда в "обоих направлениях" существуют ребра, например, что происходит в алгоритме, когда ребро и его реверс находятся на графике. Я предполагаю, что c (u, v) в минимуме для исходных емкостей в графе. Должен ли я каким-то образом обрабатывать четыре ребра в остаточном графе для случая, когда оба (a, b) и (b, a) являются ребрами? На данный момент в моей настройке я не могу напрямую обрабатывать параллельные ребра.

Я нашел следующий вопрос о SO: Максимальный поток - Ford-Fulkerson: Неограниченный график Но я не понимаю, каков результат.

Ответы

Ответ 1

Нигде в псевдокоде нет предположения о том, является ли граф циклическим или имеет "обратные ребра". Есть только края.

Если в "обоих направлениях" есть ребра, то c (u, v) и c (v, u) будут различны. c (u, v) - это просто емкость ребра от u до v, а c (v, u) - емкость ребра от v до u. Они не имеют больше отношения друг к другу, чем к другим краям.

Иными словами, оба c (u, v) и f [u, v] фактически являются функциями на ребрах, а не в вершинах. (И я думаю, что алгоритм был бы более ясен, если бы он был написан таким образом.) Поэтому подумайте о них как c (E) и f [E], где E - ребро. "Остаточная сеть" также представляет собой набор ребер, а не вершин. Остаточная сеть - это всего лишь все ребра, такие, что c (E) - f [E] положительна.

Все, что делает алгоритм, это найти любой путь от источника к цели, который все еще имеет некоторую резервную емкость, а затем увеличить поток, чтобы потреблять эту свободную емкость. f [E] - поток через край. Итак, найдите любой путь от s до t, где все f [E] меньше c (E), возьмите наименьшую разницу вдоль этого пути и увеличьте поток по этому пути этой разницей. Итерайте до тех пор, пока не останется никаких путей с резервной емкостью.

Если E и E 'являются двумя ребрами, которые обращены друг к другу, алгоритм не волнует; он рассматривает их как независимые ребра.

Понимание того, что делает алгоритм, является легкой частью. Доказывая, что он сходится, доказывая, что он получает правильный ответ, а анализ его времени работы - это тяжелые части.

[обновление]

А, я вижу; f [u, v] действительно является потоком от u до v, а не потоком вдоль ребра (так как могут быть два ребра, соединяющие u и v в противоположных направлениях).

Я думаю, вы можете просто поддерживать f [u, v] на основе вершин, но график затрат и остаточный график по-прежнему должны основываться на ребрах. Итак, в основном выполните то, что говорит алгоритм: для каждого ребра E = (u, v) на пути найдите минимум c (u, v) -f [u, v] и соответствующим образом обновите значения f []. Затем вычислите новый остаточный граф, основанный на ребрах исходного графа; т.е. для каждого ребра E = (u, v), если c (u, v) больше f [u, v], то E является членом остаточного графа.