c++algorithmgraphford-fulkersonedmonds-karp

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


Solution

  • 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.