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