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