1

Ford-Fulkersons アルゴリズムを 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/

4

2 に答える 2

2

エッジに沿っていずれかの方向に流れを押すことができる場合、A から B への正味の流れは、B から A への正味の流れと大きさが等しく、符号が反対でなければなりません。

回路解析と同じです。A から B に 5 アンペアの電流が流れる場合、B から A に -5A の電流が流れます。

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

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

したがって、A から B に「さらに」プッシュすることで、B から A にプッシュする量を対応する量だけ減らす必要があります。

于 2016-04-14T08:22:51.577 に答える
0

https://github.com/mission-peace/interview/blob/master/src/com/interview/graph/FordFulkerson.javaを参照でき ます。

ビデオの場合 https://www.youtube.com/watch?v=GiN3jRdgxU4

于 2016-04-14T07:34:31.663 に答える