Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Why must back-edges be taken into account in Edmonds-Karp Maximum Flow?

I was trying to implement Edmonds-Karp in C++ for maximum flow, and I wrote it slightly differently:

  1. Instead of going through all edges in residual graph, I only went through the edges that are present in the original graph, using the adjacency list.
  2. I did not update any back-edges when updating the residual graph with min flow.

Interestingly, when I ran my code, it gave me correct results. So I went to Wikipedia's example, where it specifically show how a back-edge is being used. When I fed this graph to my code, I got the correct answer again. I also checked the resultant flow matrix, and it was identical to Wikipedia's.

Can someone explain why we must add and update back-edges, and maybe give an example where they are critical?

Here's the code that I wrote (updated to include back edges):

like image 276
xyz Avatar asked Aug 09 '16 06:08

xyz


People also ask

Why do we need back edge?

Back edges are necessary when doing the Ford-Fulkerson algorithm in case the path that you choose ends up not being a part of the overall flow. There are no more s-t paths, but that doesn't mean you have a max flow.

What is the purpose of reversed edges in flow networks?

Back edges are there to allow you to reverse some of the flow that you might have pumped in previous stages in order to be able to increase the total flow of the network (because an augmenting path in the residual network is found).

What is the relationship between the Ford-Fulkerson method and the Edmonds-Karp algorithm?

The Edmonds-Karp Algorithm is a specific implementation of the Ford-Fulkerson algorithm. Like Ford-Fulkerson, Edmonds-Karp is also an algorithm that deals with the max-flow min-cut problem. Ford-Fulkerson is sometimes called a method because some parts of its protocol are left unspecified.


1 Answers

Consider the following flow network enter image description here

Suppose the first flow is s → u → v → t. (If you object that that the BFS of Edmonds-Karp would never choose this, then augment the graph with some more vertices between s and v and between u and t).

Without reversing flow u → v, it is impossible to obtain the optimal flow of 20.

like image 158
Ami Tavory Avatar answered Sep 21 '22 06:09

Ami Tavory