福特Fulkerson增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

如果你可以沿着邊緣推在任何一個方向流動，那麼淨流量從A到B必須與B到A的淨流量在幅度上相等且符號相反。

這就像在電路分析中一樣：如果5安培的cu從A rrent流向B，然後從B到A的電流流動的-5A

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

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

因此，通過推動「更多」從A到B，則必須減少不同於乙推至A由量相應的數量。

Answer 2

你可以參考 https://github.com/mission-peace/interview/blob/master/src/com/interview/graph/FordFulkerson.java

和視頻 https://www.youtube.com/watch?v=GiN3jRdgxU4