7    VisuAlgo.net / /maxflow Login 最大流/最小割
示例模式 ▿


go to beginning previous frame pause play next frame go to end

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.

Print this e-Lecture
X Esc
下一个 PgDn

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.

Print this e-Lecture
X Esc
上一个 PgUp
下一个 PgDn

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.

Print this e-Lecture
X Esc
上一个 PgUp
下一个 PgDn

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.
Print this e-Lecture
X Esc
上一个 PgUp
下一个 PgDn

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.
Print this e-Lecture
X Esc
上一个 PgUp
下一个 PgDn

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.

Print this e-Lecture
X Esc
上一个 PgUp
下一个 PgDn
Print this e-Lecture
X Esc
上一个 PgUp
下一个 PgDn

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).

Print this e-Lecture
X Esc
上一个 PgUp
下一个 PgDn

Control the animation with the player controls! Keyboard shortcuts are:

Spacebar: play/pause/replay
Left/right arrows: step backward/step forward
-/+: decrease/increase speed
Print this e-Lecture
X Esc
上一个 PgUp
下一个 PgDn

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.

Print this e-Lecture
X Esc
上一个 PgUp








left 1

right 1

all 1

CP3 4.24*

CP3 4.26.1 (s-lim)

CP3 4.26.2 (t-lim)

CP3 4.26.3

Ford Fulkerson Killer

Dinic Showcase

s = , t =


Ford Fulkerson

Edmonds Karp


关于 团队 使用条款


VisuAlgo在2011年由Steven Halim博士概念化,作为一个工具,帮助他的学生更好地理解数据结构和算法,让他们自己和自己的步伐学习基础。
VisuAlgo包含许多高级算法,这些算法在Steven Halim博士的书(“竞争规划”,与他的兄弟Felix Halim博士合作)和其他书中讨论。今天,一些高级算法的可视化/动画只能在VisuAlgo中找到。
zh, id, kr, vn, th.


Dr Steven Halim, Senior Lecturer, School of Computing (SoC), National University of Singapore (NUS)
Dr Felix Halim, Software Engineer, Google (Mountain View)

本科生研究人员 1 (Jul 2011-Apr 2012)
Koh Zi Chun, Victor Loh Bo Huai

最后一年项目/ UROP学生 1 (Jul 2012-Dec 2013)
Phan Thi Quynh Trang, Peter Phandi, Albert Millardo Tjindradinata, Nguyen Hoang Duy

最后一年项目/ UROP学生 2 (Jun 2013-Apr 2014)
Rose Marie Tan Zhao Yun, Ivan Reinaldo

本科生研究人员 2 (May 2014-Jul 2014)
Jonathan Irvin Gunawan, Nathan Azaria, Ian Leow Tze Wei, Nguyen Viet Dung, Nguyen Khac Tung, Steven Kester Yuwono, Cao Shengze, Mohan Jishnu

最后一年项目/ UROP学生 3 (Jun 2014-Apr 2015)
Erin Teo Yi Ling, Wang Zi

最后一年项目/ UROP学生 4 (Jun 2016-Dec 2017)
Truong Ngoc Khanh, John Kevin Tjahjadi, Gabriella Michelle, Muhammad Rais Fathin Mudzakir

List of translators who have contributed ≥100 translations can be found at statistics page.



这项工作在2012年ACM ICPC世界总决赛(波兰,华沙)和IOI 2012年IOI大会(意大利Sirmione-Montichiari)的CLI讲习班上进行了简要介绍。您可以点击此链接阅读我们2012年关于这个系统的文章(它在2012年还没有被称为VisuAlgo)。
这项工作主要由我过去的学生完成。最近的最后报告是:Erin,Wang Zi,Rose,Ivan。
VisuAlgo不是一个完成的项目。 Steven Halim博士仍在积极改进VisuAlgo。如果您在使用VisuAlgo并在我们的可视化页面/在线测验工具中发现错误,或者如果您想要求添加新功能,请联系Dr Steven Halim博士。他的联系邮箱是他的名字加谷歌邮箱后缀:StevenHalim@gmail.com。