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):
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.