Maximum Flow Problem

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

Footnotes
1.
Max Flow Ford Fulkerson | Network Flow | Graph Theory, 29
Links to this page
  • Residual Edge

    The sole existence of Residual Edge is to undo or revert bad #202206091601 which doesn’t lead to #maximum flow. The Residual Edge is valid to be included into the augmentation in the later iteration (the edge has been taken at least once). When reverting, add the flow value of the residual edge to the flow edge. It is to avoid having a negative remaining capacity# (the difference of the flow edge’s maximum capacity and flow value).

  • Ford-Fulkerson Algorithm

    Ford-Fulkerson Algorithm is a 202204151143# aim to solve #202206091105 by repeatedly finds augmenting paths through the 202206091605# and augments (updates) the flow until there is no 202206091601# to be found. It is essentially finding the bottlenecks, that is the smallest maximum capacity in the augmenting path, and sum them all together to get the maximum flow for the #202204112045. *

  • Flow Graph

    The maximum capacity for an edge must not be negative. The flow value for the edge should be less than or equal to the maximum capacity that it can allow, and the flow value from every edge must be initialised to 0 before the #calculation.

  • Depth First Search (DFS)
    solving 202206091105#
  • Augmenting Path

    Augmenting Path is a path of edges in the 202206091605# with unused capacity more than 0 from source \(s\) to sink \(t\). If Augmenting Path is exhausted, that is there is no Augmenting Path could be found, this means that we have found the #maximum flow for the #202204112045.

#graph #networking #planning #) #algorithm