Edmonds-Karp法
Abstract
Edmonds-Karp法は, 辺容量$ cが与えられたネットワーク$ \mathcal{N} = \left((V, E), c \right)に対する最大フロー問題を解くためのアルゴリズム. 特に, 増大路は幅優先探索で選択する. 辺容量がすべて正整数なら$ O(|V||E|^2)timeで解を出力する. Explanation
TODO 書く.
Algorithm (Edmonds-Karp)
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
$ O(|V||E|^2)time.
code:python
from collections import deque
class EdmondsKarp:
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
parent = -1 * self.N # parent of each vertex in the bfs search tree revs = -1 * self.N # index of the reverse edge of each vertex in the bfs search tree E = self.E
num = 0 # current ordering
while q:
v, p, f, rev = q.popleft()
if not visitedv: # visited v for the first time visitedv = True; parentv = p; revsv = rev if v == t:
aug_flow = f; break
for u, cap, rev_idx in Ev: if cap == 0 or visitedu: continue q.append((u, v, min(f, cap), rev_idx))
if aug_flow:
v, p, rev = t, parentt, revst while p != -1:
e1 -= aug_flow; rev_e1 += aug_flow v, p, rev = p, parentp, revsp 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.