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

Question

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

Answer 1

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.

Answer 2

try out the following case:

int main() {
    Digraph<int> g(8);
    g.addEdge(0,1,1);
    g.addEdge(1,2,1);
    g.addEdge(2,4,1);
    g.addEdge(0,3,1);
    g.addEdge(3,4,1);
    g.addEdge(4,7,1);
    g.addEdge(3,5,1);
    g.addEdge(5,6,1);
    g.addEdge(6,7,1);

    cout<<g.maxFlowEdmondsKarp(0,7);

    return 0;
}

Visualization:

your program takes the shortest way 0-3-4-7 first and has then no chance to find 0-1-2-4-7 and 0-3-5-6-7. You get 1 but 2 would be the right answer.

Would you have inserted the back-edge, then you would find the following paths:

1. 0-3-4-7
2. 0-1-2-4-3(back-edge!)-5-6-7, getting the max flow 2.