最大流問題

連結グラフ G=(V,E), 容量 c:E->R+, および, 2つの頂点 s と t が与えられたとき、最大 s-t 流を求めよ。

最小カット問題

連結グラフ G=(V,E), 容量 c:E->R+, および, 2つの頂点 s と t が与えられたとき、最小 s-t カットを求めよ。

フォード・ファルカーソンのラベリングアルゴリズム

  1. (Initialization) Let x be an initial feasible flow (e.g. x(e) = 0 for all e in E).
  2. (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 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

  1. (Initialization) Let x be an initial feasible flow (e.g. x(e) = 0 for all e in E).
  2. (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 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