Ford-Fulkerson 法

これはステージング環境です。5 秒後に自動的に本番環境 (https://dic.kimiyuki.net) にリダイレクトされます。リダイレクトを抑止したい場合は #noredirect を付けた URL /ford-fulkerson#noredirect を利用してください。
name
Ford-Fulkerson 法
short description
Ford-Fulkerson 法は最大流問題を解くアルゴリズムのひとつ。 増加パスを DFS で探してそこにフローを流していくことを繰り返す。 計算量は出力の $s$-$t$ 最大流量を $F$ として $O(F \cdot \lvert E \rvert)$ である。
input
辺容量が整数であるネットワーク (つまり有向グラフ $G = (V, E)$ および辺容量 $c : E \to \mathbb{N}$ および相異なる頂点 $s, t \in V$)
output
$s$-$t$ 最大流 (つまり関数 $f : E \to \mathbb{N}$ であって容量制約とフロー保存則を満たすもの)
time complexity
出力の $s$-$t$ 最大流量を $F$ として $O(F \cdot \lvert E \rvert)$

概要

Ford-Fulkerson 法は最大流問題を解くアルゴリズムのひとつである。 残余グラフ上で増加パスを DFS で探しそこにフローを流していくことを繰り返す。 計算量は出力の $s$-$t$ 最大流量を $F$ として $O(F \cdot \lvert E \rvert)$ である。

詳細

(省略)

関連項目

外部リンク