Here we setup the language of a flow network, identify what we are looking for, examine a natural greedy approach that doesn't work, and fix it so we get to the Ford-Fulkerson algorithm. By making some specific choices in this algorithm we obtain the Edmonds-Karp algorithm.
The module is split into three segments:
- Introduction to the maxflow problem
- Algorithms for maxflow
- Implementing Edmonds-Karp
The code shown in these lectures can be found here. You can try it yourself via the UVa 820 problem, Internet Bandwidth.
Although not discussed, you can find the code for Dinic's algorithm here.
Other sources to learn about maxflow:
Max Flow Ford Fulkerson | Network Flow | Graph Theory
Explanation of how to find the maximum flow with the Ford-Fulkerson methodSupport me by purchasing the full graph theory course on Udemy which includes addit...
Edmonds Karp Algorithm | Network Flow | Graph Theory
Explanation video of the Edmonds-Karp network flow algorithmSupport me by purchasing the full graph theory course on Udemy which includes additional problems...