Dinitz法
#Graph #Algorithm #Network_Flow #BFS #DFS
Abstract
Dinitz法は, 辺容量$ cが与えられたネットワーク$ \mathcal{N} = \left((V, E), c \right)に対する最大フロー問題を解くためのアルゴリズム. ブロッキングフローを構成することでフローを更新する. 辺容量がすべて正整数なら$ O(|V|^2|E|)timeで解を出力する.Dinicと表記されることも多い.
Explanation
TODO 書く.
Algorithm (Dinitz)
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-増大路を幅優先探索を利用して探す. 増大路が存在しなければ, $ fと現在のフロー流量$ |f|を出力して終了.
3. 残余ネットワーク$ \mathcal{N}_fのレベルネットワーク$ \tilde{\mathcal{N}}_fを構成し, $ \tilde{\mathcal{N}}_fのブロッキングフロー$ \phiを見つけ, $ f \gets f \oplus \phiと更新する. 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|^2|E|)time.
code:python
from collections import deque
class Dinitz:
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 _exist_augpath(self, s, t):
self.level = level = -1 * self.N # the level (depth) of each vertex
E = self.E
q = deque((s, 0)) # (vertex, level)
while q:
v, lv = q.popleft()
if levelv < 0: # visited v for the first time
levelv = lv
for u, cap, _ in Ev:
if cap == 0 or levelu >= 0: continue
q.append((u, lv + 1))
return levelt >= 0
def _blocking_flow(self, s, t):
aug_flow = 0
finished = False * self.N
parent = -1 * self.N
revs = -1 * self.N
bottleneck = -1; temp_flow = 0
E, level = self.E, self.level
stack = (s, -1, float('inf'), -1, 0) # (vertex, parent, flow, rev_idx, status)
while stack:
v, p, f, rev, st = stack.pop()
if temp_flow and v != bottleneck: continue
if st == 0 and not finishedv:
parentv = p; revsv = rev
if temp_flow: # offset
f -= temp_flow; temp_flow = 0; bottleneck = -1
if v == t: # an augment path is found
aug_flow += f
if p != -1: stack += (v, p, f, rev, 3)
continue
n_children = 0
for u, cap, rev_idx in Ev:
if cap == 0 or finishedu or levelu != levelv + 1: 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
if n_children == 0: # v is a leaf
finishedv = True
elif st == 1: # now searching
continue
elif st == 2: # search finished
finishedv = True
else: # edge update
rev_e = Evrev; e = Ep[rev_e2]
e1 -= f; rev_e1 += f
if e1 == 0: bottleneck = p
if parentp != -1: stack += [(p, parentp, f, revsp, 3)]
else: temp_flow = f
return aug_flow
def max_flow(self, s, t):
flow = 0
exist_augpath, blocking_flow = self._exist_augpath, self._blocking_flow
while True:
if not exist_augpath(s, t): break # no augment path is found
flow += blocking_flow(s, t)
return flow
Verification
最大流
References
ACM-ICPC: Dinic's Algorithm
Dinic法
最大流問題
ネットワークフロー入門
T. Cormen, C. Leiserson, R. Rivest, and C. Stein, 『アルゴリズムイントロダクション 第3版』, 近代科学社, 2009.
R. E. Tarjan, 『新訳 データ構造とネットワークアルゴリズム』毎日コミュニケーションズ, 2008.
繁野麻衣子, 『ネットワーク最適化とアルゴリズム』, 朝倉書店, 2010.