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

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

10 голосов
/ 12 октября 2011

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

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

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

1 Ответ

5 голосов
/ 12 октября 2011

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

Если есть ребра в «обоих направлениях», то 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 является членом остаточного графа.

...