Maximum (Max) Flow is one of the problems in the family of problems involving flow in networks.
In Max Flow problem, we aim to find the maximum flow from a particular source vertex s to a particular sink vertex t in a weighted directed graph G.
There are several algorithms for finding the maximum flow including Ford Fulkerson's method, Edmonds Karp's algorithm, and Dinic's algorithm (there are others, but not included in this visualization yet).
The dual problem of Max Flow is Min Cut, i.e. by finding the max s-t flow of G, we also simultaneously find the min s-t cut of G, i.e. the set of edges with minimum weight that have to be removed from G so that there is no path from s to t in G.
This visualization page will show the execution of a chosen Max Flow algorithm running on a flow (residual) graph.
The input for a Max Flow algorithm is a flow graph (a directed graph G = (V, E) where edge weight represent the (unit) capacity of flow that can go through that edge) with two distinguished vertices: The source vertex s and the sink/target/destination vertex t.
To make the visualization of these flow graphs consistent, we enforce a graph drawing rule for this page whereby the source vertex s/sink vertex t is always vertex 0/V-1 and is always drawn on the leftmost/rightmost side of the visualization, respectively.
Another constraint is that the edge capacities are integers between [1..99].
Pro-tip: Since you are not logged-in, you may be a first time visitor who are not aware of the following keyboard shortcuts to navigate this e-Lecture mode: [PageDown] to advance to the next slide, [PageUp] to go back to the previous slide, [Esc] to toggle between this e-Lecture mode and exploration mode.
At the start of the three Max Flow algorithms discussed in this visualization (Ford Fulkerson's method, Edmonds Karp's algorithm, and Dinic's algorithm), the initial flow graph is converted into residual graph.
The edges in the residual graph store the remaining capacities of those edges that can be used by future flow(s). At the beginning, these remaining capacities equal to the original capacities as specified in the input flow graph.
A Max Flow algorithm will send flows to use some (or all) of these available capacities, iteratively.
Once the remaining capacity of an edge reaches 0, that edge can no longer admit any more flow.
Another pro-tip: We designed this visualization and this e-Lecture mode to look good on 1366x768 resolution or larger (typical modern laptop resolution in 2017). We recommend using Google Chrome to access VisuAlgo. Go to full screen mode (F11) to enjoy this setup. However, you can use zoom-in (Ctrl +) or zoom-out (Ctrl -) to calibrate this.
There are three different sources for specifying an input graph:
There are three different max flow algorithms in this visualization:
For the three Max Flow algorithms discussed in this visualization, successive flows are sent from the source vertex s to the sink vertex t via available augmenting paths.
The three Max Flow algorithms in this visualization have different behavior on how they find augmenting paths.
However, all three Max Flow algorithms in this visualization stop when there is no more augmenting path possible and report the max flow value (and the assignment of flow on each edge in the flow graph).
Later we will discuss that this max flow value is also the min cut value of the flow graph.
e-Lecture: The content of this slide is hidden and only available for legitimate CS lecturer worldwide. Drop an email to visualgo.info at gmail dot com if you want to activate this CS lecturer-only feature and you are really a CS lecturer (show your University staff profile).
Control the animation with the player controls! Keyboard shortcuts are:
Return to 'Exploration Mode' to start exploring!
Note that if you notice any bug in this visualization or if you want to request for a new visualization feature, do not hesitate to drop an email to the project leader: Dr Steven Halim via his email address: stevenhalim at gmail dot com.