Understanding reverse edges in Ford-Fulkerson method


The Ford-Fulkerson method to find the maximum flow in a graph makes use of reverse edges when simulating flow in the graph. The reverse edges are crucial as they allow reducing already simulated flow in some edges if more total flow can be simulated in the graph as a result. Let's look at an example to understand it better. Given below is a flow graph and the maximum flow that can flow through it.

Loading Image

A flow network and the maximum flow through it.

In every iteration of the Ford-Fulkerson method, we try to find an augmenting path in the residual graph. It is important to note that while there may be multiple augmenting paths, we choose the first one we find. We call this path p1.

Liking the course? Check our discounted plans to continue learning.