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.

Remarks: By default, we show e-Lecture Mode for first time (or non logged-in) visitor.
Please login if you are a repeated visitor or register for an (optional) free account first.

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:

1. Draw Graph: You can draw any directed weighted graph as the input graph with vertex 0 as the default source vertex (left side of the screen) and vertex V-1 as the default sink vertex (right side of the screen),
2. Modeling: Several graph problems can be reduced into a max flow problem. In this visualization, we have the modeling examples for the famous Maximum Cardinality Bipartite Matching (MCBM) problem, Rook Attack problem (currently disabled), and Baseball Elimination problem (currently disabled),
3. Example Graphs: You can select from the list of our selected example flow graphs to get you started.

There are three different max flow algorithms in this visualization:

1. The slow O(mf * E) Ford Fulkerson's method,
2. The O(V * E^2) Edmonds Karp's algorithm, or
3. The O(V^2 * E) Dinic's algorithm.

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.

You are allowed to use/modify our implementation code for Max Flow Algorithms (Edmonds-Karp/Dinic's):
maxflow.cpp
maxflow.java
maxflow.py
maxflow.ml