そのうち誰かの役に立つ

もしくは誰の役にも立たない

Ford-Fulkerson

アルゴリズムとデータ構造 Ford-Fulkerson Python3 Go

概要

  • 各辺に容量を持ち、始点と終点のあるグラフが与えられたとき、始点から終点までの最大フローを求める
  • 最大フロー最小カット定理により、グラフの最小カットを求めることとも同値
  • グラフ中の辺 uv の容量が c で、 u から v に f だけフローが流れているとき、 u \gets v に c - f の有効辺を考える
    • あとどれくらいフローを流せるかを意味するネットワークが構築できる
    • 残余ネットワークなどと呼ばれる
  • 残余ネットワークにおいて終点から始点へのパスを見つけ、そのパス上にフローを流すことを繰り返す
    • このようなパスを増加パス（増加道）などと呼ぶ
    • フローを流すたびに残余ネットワークを更新していく
    • パスの探索に幅優先探索を用いる場合をEdmonds-Karpと呼ぶこともある
  • 計算時間はグラフの辺の数を E、最大フローを F として O(EF)
    • 1回の残余ネットワークの探索に O(E)、1回パスを見つけるごとにフロー量は少なくとも1増加するので、繰り返しは最大でも F 回
    • 辺の容量が無理数の場合は停止性が保証されない
    • Edmonds-Karpではグラフの頂点数を V、辺の数を E として O(VE^{2}) で、停止性が保証される

実装

  • InitGraph(N) で N 点の頂点集合を作り、AddEdge(u, v, c) で頂点 u から頂点 v へ容量 c の辺を作る
  • FordFulkerson(s, t) で s から t への最大フローを求める
  • 良い感じの例題を作るのが難しかったので、ライブラリ部分だけ記載

Python3で実装する

Powered by OnlineGDB

Goで実装する