最大流を求めるアルゴリズムの歴史

フォード・ファルカーソンのアルゴリズム - Wikipedia

容量が無理数の場合、停止しない可能性がある

容量が整数の場合、最大フローをfとしてO(Ef)

これは1ステップごとにフローが増加することによる

有理数の場合は適当に整数を掛ければ整数になる

エドモンズ・カープのアルゴリズム - Wikipedia

フォード・ファルカーソンのアルゴリズムとほぼ同じ

スタートから最初に幅優先探索して距離を求めておく

増加道の探索の際にスタートから遠ざかる方向にだけ探索する

エドモンズ・カープのアルゴリズムとほぼ同じ

さらにO(VElogV)にすることもできる

nishio

	[フォード・ファルカーソンのアルゴリズム - Wikipedia https://ja.wikipedia.org/wiki/%E3%83%95%E3%82%A9%E3%83%BC%E3%83%89%E3%83%BB%E3%83%95%E3%82%A1%E3%83%AB%E3%82%AB%E3%83%BC%E3%82%BD%E3%83%B3%E3%81%AE%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0]

  容量が無理数の場合、停止しない可能性がある

  容量が整数の場合、最大フローをfとしてO(Ef)

   これは1ステップごとにフローが増加することによる

   有理数の場合は適当に整数を掛ければ整数になる

 [エドモンズ・カープのアルゴリズム - Wikipedia https://ja.wikipedia.org/wiki/%E3%82%A8%E3%83%89%E3%83%A2%E3%83%B3%E3%82%BA%E3%83%BB%E3%82%AB%E3%83%BC%E3%83%97%E3%81%AE%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0]

   フォード・ファルカーソンのアルゴリズムとほぼ同じ

  	スタートから最初に幅優先探索して距離を求めておく

  	　増加道の探索の際にスタートから遠ざかる方向にだけ探索する

 		[Edmonds–Karp algorithm - Wikipedia https://en.wikipedia.org/wiki/Edmonds%E2%80%93Karp_algorithm]

 [Dinic's algorithm - Wikipedia https://en.wikipedia.org/wiki/Dinic%27s_algorithm]

 	エドモンズ・カープのアルゴリズムとほぼ同じ

 		さらにO(VElogV)にすることもできる

Related Pages