Slides:
https://www2.compute.dtu.dk/courses/02110/2023/slides/flow1-1x1.pdf
Problems:
https://www2.compute.dtu.dk/courses/02110/2023/weekplans/network1.pdf
• KT 7.1, Page 338
• KT 7.2, Page 346
Max Flow Ford Fulkerson | Network Flow | Graph Theory
Key terms: Backward edge. Going in to opposite direction (undo a flow)
If the forward paths are full and the backward path are empty the algorithm is done.
You can choose different paths but should end up with the same flow value
If you code the algorithm you will likely use DFS at each iteration to find the path
Time Comlexity: O(E·f)
E = # of edges
f = maximum flow
What is max flow and minimum cut: Smallest capacity cut, ST-cut,
Max flow = min cut = 4
Edmonds Karp Algorithm | Network Flow | Graph Theory
BFS instead of DFS, because of time complexity