Question: I was trying to implement [**Edmonds-Karp**](https://en.wikipedia.org/wiki/Edmonds%E2%80%93Karp_algorithm) 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](https://en.wikipedia.org/wiki/Edmonds%E2%80%93Karp_algorithm#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](https://github.com/prakharsingh95/Graph-Implementations/blob/master/src/max_flow_ford_fulkerson.cpp)'s the code that I wrote (updated to include back edges):

Answer: 
Consider the following flow network
[![enter image description here](https://i.stack.imgur.com/1R1dv.jpg)](https://i.stack.imgur.com/1R1dv.jpg)

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.
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:
[![enter image description here](https://i.stack.imgur.com/5Zktk.png)](https://i.stack.imgur.com/5Zktk.png)

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.