フォード - フルカーソンの実装のJava

Question

私はJavaでフォード-Fulkersonsアルゴリズムを実装するために学ぼうと、インターネット上でいくつかの助けを見つけましたが、私は、私は一種の理解コード

 // 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/

Answer 1

のために参照することができますBは、BからAへの正味の流れと大きさが等しく、符号が反対でなければなりません。

これは回路解析のようなものです：もし5アンペアのcu BからAへの電流の流れのBまで、次に-5Aからrrent流

したがって

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

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

、Bから「より多くの」を押すことによって、あなたがによってBからプッシュされる量を低減する必要が対応する量。

Answer 2

あなたは https://github.com/mission-peace/interview/blob/master/src/com/interview/graph/FordFulkerson.java

とビデオ https://www.youtube.com/watch?v=GiN3jRdgxU4