Ford-Fulkerson Implementierung Java

Question

ich den Ford-Fulkersons Algorithmus in Java zu lernen, bin versucht zu implementieren und etwas Hilfe im Internet zu finden, aber ich in diesem Code-Snippet

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

ich irgendwie stecken geblieben verstehen wie es funktioniert dank dem Kommentar, aber nicht ganz sicher, warum es erforderlich ist. Warum müssen Sie subtrahieren?

Quelle: http://www.geeksforgeeks.org/ford-fulkerson-algorithm-for-maximum-flow-problem/

Answer 1

Wenn Sie einen Fluss in beide Richtungen entlang einer Kante schieben, dann den Nettofluss von A nach B muss gleich groß und entgegengesetzt im Vorzeichen zum Nettofluss von B nach A sein.

Es ist wie in der Schaltungsanalyse: wenn 5 Ampere Cu rrent Fluss von A nach B, dann -5A Stromflußrichtung von B nach A.

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

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

daher durch „mehr“ von A nach B gedrückt wird, muss die Menge verringern, dass drängen von B nach A durch ein entsprechender Betrag.

Answer 2

Sie sich beziehen können https://github.com/mission-peace/interview/blob/master/src/com/interview/graph/FordFulkerson.java

und für Video https://www.youtube.com/watch?v=GiN3jRdgxU4