Ford-Fulkerson法
Abstract
Ford-Fulkerson法は, 辺容量$ cが与えられたネットワーク$ \mathcal{N} = \left((V, E), c \right)に対する最大フロー問題を解くためのアルゴリズム. 特に, 増大路は深さ優先探索で選択する. 最大フローを$ f^*とすると, 辺容量がすべて正整数なら$ O(|f^*||E|)timeで解を出力する. Explanation
TODO 書く.
Algorithm (Ford-Fulkerson)
Input:
辺容量$ cが与えられたネットワーク$ \mathcal{N} = \left((V, E), c \right)
ソース$ s \in V
シンク$ t \in V
Output:
$ s,t-最大フローの流量 $ |f^*|
1. フロー$ f を$ f(e) \gets 0 と初期化する.
2. フロー$ f について, 残余ネットワーク$ \mathcal{N}_f = \left((V, E_f), c_f \right)を構成し, $ \mathcal{N}_fの$ s,t-増大路$ Pを深さ優先探索を利用して探す. 増大路が存在しなければ, $ fと現在のフロー流量$ |f|を出力して終了. 3. $ \varepsilon \gets \min \{ c_f(e) \mid e \in E_f \cap P \}とし, $ Pに沿って$ \varepsilonだけフローを流すことで$ fを更新する. 2へ戻る.
Implementation
グラフ構築
Input
グラフの頂点数 N
グラフの各有向辺の始点 init, 終点 end, 重み capacity
capacity は正整数である必要がある.
Output
グラフの隣接リスト E
Time complexity
$ O(|E|)time.
最大フローの流量計算
Input
ソース s とシンク t
Output
s, t-フローの最大流量 flow
Time complexity
最大フローを$ f^*とすると, $ O(|f^*||V|)time.
code:python
class FordFulkerson:
def __init__(self, N):
self.N = N
self.E = [[] for _ in range(N)]
def add_edge(self, init, end, capacity):
'''
e0 = the head vertex of e, e1 = current capacity of e, e2 = the index of reverse edge of e. '''
self.Einit.append([end, capacity, len(self.Eend)]) self.Eend.append([init, 0, len(self.Einit) - 1]) def _augpath_flow(self, s, t):
aug_flow = 0
E = self.E
while stack:
v, p, f, rev, st = stack.pop()
if st == 0 and not visitedv: # visited v for the first time if aug_flow: continue # no need to check new vertices
if v == t: # augment path is found
aug_flow = f
e1 -= aug_flow; rev_e1 += aug_flow continue
n_children = 0
for u, cap, rev_idx in Ev: if cap == 0 or visitedu: continue if n_children == 0:
stack += (v, p, 0, rev, 2), (u, v, min(f, cap), rev_idx, 0) n_children += 1
else:
stack += (v, p, 0, rev, 1), (u, v, min(f, cap), rev_idx, 0) n_children += 1
elif st == 2: # search finished
if aug_flow and p != -1:
e1 -= aug_flow; rev_e1 += aug_flow return aug_flow
def max_flow(self, s, t):
flow = 0
augpath_flow = self._augpath_flow
while True:
f = augpath_flow(s, t)
if f: flow += f
else: break
return flow
Verification
References
T. Cormen, C. Leiserson, R. Rivest, and C. Stein, 『アルゴリズムイントロダクション 第3版』, 近代科学社, 2009.
R. E. Tarjan, 『新訳 データ構造とネットワークアルゴリズム』毎日コミュニケーションズ, 2008.
繁野麻衣子, 『ネットワーク最適化とアルゴリズム』, 朝倉書店, 2010.