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

Question

Я пытаюсь научиться реализовать алгоритм Форда-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/

Answer 1

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

Это как в анализе схемы: если 5 ампер cu Поток от ко в ой то А к В, то -5A тока от В к А.

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

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

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

Answer 2

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

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