I was trying to implement Edmonds-Karp in C++ for maximum flow, and I wrote it slightly differently:
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):
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.
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).
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.
Consider the following flow network
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.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With