いんとろ - れんしゅうちょう。

2014-03-11最大流問題について.

■ いんとろ 02:05

最大流問題を解くアルゴリズムについて, ちょろっと書いておきます.

要約すると, 言いたいことは

Dinic のライブラリ持ってたら, 間違っていないかチェックしましょう. (注意1のやつ)
Dinic ちょっぱやな気がするけど, ワーストケースは遅いよ. (当然)

の二つです. 半分自分用のメモみたいなもんです.

Dinic についてちゃんと知っている人が読むメリットは多分無いです.

ツッコミなどあれば, ぜひお願いします.

蟻本のページ番号が書いてある時は, 第二版のものです.

最大流問題を知らない人は, 蟻本(p. 188から少し)を読んで下さい.

今回は, グラフ $G=(V, E)$ 上で, $S$ から $T$ への最大流を求めたいとします.

また, $n = |V|$ , $m = |E|$ とします. (こんな準備要るのかな)

コメントを書く

7742015/10/15 23:28「Dinic 法と, その注意点」の注意2の部分について
探索順序は
S, a, b, a, e, a, S, b, e, b, f, b, S, c, g, T, g, c, h, T, h, c, S
ではないですか？最初に g に来たときに c に戻るのはなぜでしょうか．
私が理解していない/勘違いしていたら済みません．

Mi_Sawa2015/10/15 23:39(最初の b が d ですが)そのとおりですね. ご指摘ありがとうございます, 修正します.