最大流問題
連結グラフ G=(V,E), 容量 c:E->R+, および, 2つの頂点 s と t
が与えられたとき、最大 s-t 流を求めよ。
最小カット問題
連結グラフ G=(V,E), 容量 c:E->R+, および, 2つの頂点 s と t
が与えられたとき、最小 s-t カットを求めよ。
フォード・ファルカーソンのラベリングアルゴリズム
- (Initialization) Let x be an initial feasible flow (e.g. x(e) = 0 for all e
in E).
- (Flow augmentation)
If there are no augmenting path from s to t on the residual network, then stop.
The present x is a max flow.
If there is a flow augmenting path p, replace the flow x as
- x(e)=x(e)+delta if e is a forward arc on p.
- x(e)=x(e)-delta if e is a backward arc on p.
where delta is a minimum value of residual capacity on p.
Repeat this step.
JavaScript ソースファイル:
JavaScript デモ:
Here is a JavaScript illustrating
the Ford-Fulkerson Labeling Algorithm,
which yields a max-flow and a min-cut.
関連ページ:
Maximum Flow Problem
Given a connected graph G=(V,E), a capacity c:E->R+, and two nodes s and t,
find a maximum s-t flow.
Minimum Cut Problem
Given a connected graph G=(V,E), a capacity c:E->R+, and two nodes s and t,
find a minimum s-t cut.
Ford-Fulkerson Labeling Algorithm
- (Initialization) Let x be an initial feasible flow (e.g. x(e) = 0 for all e in E).
- (Flow augmentation)
If there are no augmenting path from s to t on the residual network, then stop.
The present x is a max flow.
If there is a flow augmenting path p, replace the flow x as
- x(e)=x(e)+delta if e is a forward arc on p.
- x(e)=x(e)-delta if e is a backward arc on p.
where delta is a minimum value of residual capacity on p.
Repeat this step.
JavaScript Source files:
JavaScript Demos
Here is a JavaScript illustrating
the Ford-Fulkerson Labeling Algorithm,
which yields a max-flow and a min-cut.
See Also