Maximum Flow Problem ask: With an infinite input source (denoted \(s\)), how much flow can we push to through the network (depicted as 202206091453#), that is to the end node (sometime call sink, denoted \(t\)), given that each edge has a certain capacity (that one should not exceed)? 1
The problem can be solved various #algorithm :
- 202206091518# (resulted in \(O(fE)\))
- Edmonds-Karp (utilises BFS, resulted in \(O(E^2 V)\))
- capacity scaling (pick larger paths first, resulted in \(O(E^2 \log{V})\))
- Dinic’s algorithm (combination of BFS and #202205021959 resulted in \(O(V^2 E)\))
- push-relabel (maintain preflow instead of calculating augmented path, resulted in \(O(V^2 E)\) or \(O(V^2 \sqrt{E})\))
It is a useful model or simulation for digestion problem such as routing, #202205031213 and public transport timetable.
Aug 2018 https://www.youtube.com/watch?v=LdOnanfc5TM