Dinic 法

これはステージング環境です。5 秒後に自動的に本番環境 (https://dic.kimiyuki.net) にリダイレクトされます。リダイレクトを抑止したい場合は #noredirect を付けた URL /dinic#noredirect を利用してください。
name
Dinic 法
short description
Dinic 法は最大流問題を解くアルゴリズムのひとつ。 残余グラフ上において、辺の本数の意味での $s$-$t$ 最短経路 DAG を BFS により構成し、増加パスをこの DAG の上の DFS により探して流せるだけ流す、という一連のステップを繰り返す。 計算量は $O(\lvert V \rvert^2 \lvert E \rvert)$ だが実用的にはかなり速い。
input
ネットワーク (つまり有向グラフ $G = (V, E)$ および辺容量 $c : E \to \mathbb{R} _ {\ge 0}$ および相異なる頂点 $s, t \in V$)
output
$s$-$t$ 最大流 (つまり関数 $f : E \to \mathbb{R} _ {\ge 0}$ であって容量制約とフロー保存則を満たすもの)
time complexity
最悪計算量は $O(\lvert V \rvert^2 \lvert E \rvert)$ だが実用的にはかなり速い。ネットワークの構造によっては計算量が落ちることがある。

概要

Dinic 法は最大流問題を解くアルゴリズムのひとつである。 残余グラフ上において、辺の本数の意味での $s$-$t$ 最短経路 DAG を BFS により構成し、増加パスをこの DAG の上の DFS により探して流せるだけ流す、という一連のステップを繰り返す。

最悪計算量は $O(\lvert V \rvert^2 \lvert E \rvert)$ だが実用的にはかなり速い。また、ネットワークの構造を制限すれば最悪計算量が落ちることがある1

詳細

(省略)

関連項目

外部リンク

注釈