Ford-Fulkerson Algorithm: The Fine Print
Learn the implementation details of the Ford-Fulkerson algorithm.
Implementation details
To implement the Ford-Fulkerson algorithm, the first challenge to address is to find a semi-path from a source to a sink in a given flow network. It’s not obvious how to do this efficiently. It is easy to find outgoing edges from a vertex by traversing a single adjacency list, but finding all incoming edges on that vertex requires traversing adjacency lists of all the vertices!
A significant part of this lesson is aimed at working around the difficulty of finding semi-paths when implementing the Ford-Fulkerson algorithm.
Residual network
To avoid doing all that work, we maintain a second digraph to keep track of edges in both directions. We call this digraph a residual network. We construct a residual network for a flow network with a flow as follows:
- is just a copy of .
- For each edge in , there are two edges and in .
- We assign capacities to edges in to make it a flow network. For an edge in , the capacities assigned to corresponding two edges in are given by
The edge capacities in a residual network represent the maximum amount by which we can increase or decrease the flow along the corresponding edge in .
For example, in the following illustration, the flow along the edge in can increase by units or decrease by units. This explains the capacities of ...
Get hands-on with 1400+ tech skills courses.