dtalamas24's blog

By dtalamas24, 8 years ago, In English


  • Vote: I like it
  • -35
  • Vote: I do not like it

8 years ago, # |
Rev. 2   Vote: I like it +6 Vote: I do not like it

this is to allow flow to go back if our choice of path wasn't optimal, to see this lets check this case Lets assume we have a graph with 6 nodes and 7 edges (u v cap) (0 1 1) (0 2 1) (1 3 1) (1 4 1) (2 3 1) (3 5 1) (4 5 1) with s = 0,t = 5 if the first augmenting path we found is 0,1,3,5 and we increased flow along the edges of that path and didn't decrease flow in the opposite direction. in the second iteration we'll find no more augmenting paths. however if we decrease the flow in the opposite direction, this will allow an augmenting path 0,2,3,1,4,5 to be found and this makes the maximum flow 2.

so intuitively you may think of the decreasing flow in the reverse direction step as a way to undo any mistakes we made by taking the wrong augmenting path (the path which doesn't lead to maximum flow in the end).