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

Question

Я изучаю алгоритм Форда-Фулкерсона из книги Кормена "Введение в алгоритмы 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. (Правка: c является емкостной функцией задается при запуске и расширяется до нуля на ребрах, не являющихся частью графика)

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

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

Answer 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 является членом остаточного графа.