Форд-Фулкерсон реализация java

Я пытаюсь научиться реализовывать алгоритм Форда-Фулкерсона в Java и нашел некоторую помощь в Интернете, но я застрял в этом фрагменте кода

        // update residual capacities of the edges and
        // reverse edges along the path
        for (v=t; v != s; v=parent[v])
        {
            u = parent[v];
            rGraph[u][v] -= path_flow;
            rGraph[v][u] += path_flow;
        }

Я вроде понимаю, как это работает, благодаря комментарию, но не совсем уверен, зачем это нужно. Зачем вам нужно вычитать?

Источник: http://www.geeksforgeeks.org/ford-fulkerson-algorithm-for-maximum-flow-problem/

Источник

2 ответа

Решение

Если вы можете протолкнуть поток в любом направлении вдоль ребра, то чистый поток от A до B должен быть равен по величине и противоположен по знаку чистому потоку от B до A.

Это так же, как при анализе цепей: если 5 А тока течет от А до В, то -5 А тока течет от В до А.

A     Resistor      B
O-----[======]------O
  5A ->

A     Resistor      B
O-----[======]------O
             <- -5A

Следовательно, нажимая "больше" от А до В, вы должны уменьшить величину, толкаемую от В до А, на соответствующую величину.

Источник

Вы можете обратиться к https://github.com/mission-peace/interview/blob/master/src/com/interview/graph/FordFulkerson.java

и для видео https://www.youtube.com/watch?v=GiN3jRdgxU4

Источник
Другие вопросы по тегам