from Dinic 最大流を求めるアルゴリズムの歴史
- フォード・ファルカーソンのアルゴリズム - Wikipedia
- 1956
- 容量が無理数の場合、停止しない可能性がある
- 容量が整数の場合、最大フローをfとしてO(Ef)
- これは1ステップごとにフローが増加することによる
- 有理数の場合は適当に整数を掛ければ整数になる
- エドモンズ・カープのアルゴリズム - Wikipedia
- 1972
- O(VE^2)
- フォード・ファルカーソンのアルゴリズムとほぼ同じ
- スタートから最初に幅優先探索して距離を求めておく
- 増加道の探索の際にスタートから遠ざかる方向にだけ探索する
- Edmonds–Karp algorithm - Wikipedia
- Dinic’s algorithm - Wikipedia
- 1970
- O(V^2E)
- エドモンズ・カープのアルゴリズムとほぼ同じ
- 追加の工夫がある
- さらにO(VElogV)にすることもできる