ライブラリとして持ってはいたけど、あまり理解していなかったDinic法について学び直したのでメモ。

Dinic法とは

Dinic法は、最大フロー問題を効率的に解くためのアルゴリズムである。
最大フロー問題については、蟻本第二版188ページ参照。

概要

N個のノードのうち、ノードsからノードtへの最大流を求める問題を考える。
エッジはM本あるものとする。

データ構造

Dinic法ではM本のエッジが与えられた時、反対方向に容量0のエッジを貼って初期化する。これを逆辺と呼ぶ。エッジの情報は

struct edge {int to, cap, rev};
vector<edge> G[MAX_N];

という形で保持する。
toは行き先のノード、capはエッジの容量、revは逆辺を特定するための情報である。
例えば、e = G[n][m]でeはノードnから伸びているm本目のエッジを表す。
この時、G[e.to][e.rev]はeの逆辺を表す。

処理の流れ

最大フローを求めるアルゴリズムは大雑把にいうと次のような流れで動作する。

フローを流せるパスを適当に求めて、フローを流す。
流したエッジのcapを流した分だけ減らす。
流したエッジの逆辺のcapを流した分だけ増やす。
(capの増えた逆辺は通れるようになる)
1, 2を流せるパスがなくなるまで繰り返す

これを効率的にやるためにDinic法では幅優先探索 (dfs) と深さ優先探索 (bfs) を使う。

Dinic法の処理の流れを以下に示す。

f:id:vartkw:20161201224228p:plain

flowは求めるべき最大フローを示す。 level[t]は幅優先探索で求めたsからtまでの最短距離を示す。

以下、幅優先探索と深さ優先探索での処理について詳しく述べる。

幅優先探索

幅優先探索では始点sから各ノードまでの最短距離を求める。
配列levelの要素を-1で初期化する。
普通に幅優先探索をして、始点sからの最短距離を配列levelに格納する。
この際、(当然だが) cap > 0 && level[to] < 0となるエッジのみを遷移に使用する。
level[t]が-1のままの場合は、フローを流せるエッジが存在しないので終了。
オーダーはO(M)。幅優先探索で求められるtまでの最短距離level[t]は毎ステップで必ず増加する。
従って、この処理は高々N-1回しか呼ばれない。

深さ優先探索

深さ優先探索では逆辺を含めたcap > 0 && level[to] < level[t]となるエッジを使ったsからtまでのパス (増加パス) を一つ見つけ、その流量を調べる。
そしてエッジを更新する。
この際、調べたエッジには印をつけておく。
あるパスを採用する時、使えなくなるエッジはcapが最小の1本だけである。
そのため、深さ優先探索をもう一度行うとその使えない1本までは同じパスを調べてしまう。
そのような無駄を省くために、調べたエッジに印をつけておく。
この操作を繰り返し、流せなくなったらbfsのステップに戻る。
オーダーはO(NM)。
オーダーに関しては以下が非常にわかりやすかった。

Dinic 法と, その注意点 - れんしゅうちょう。

以上から、O(N² M)で最大流を求めることができる。
実際にはそれより高速に動作することが多いようだ。

追記:
普通に写経しても効果が薄いと思って、pythonに移植した蟻本コードのお墓。

# coding: utf-8
import queue

class Dinic:
    """Implementation of Dinic's Alogorithm"""

    def __init__(self, v, inf = 1000000007):
        self.V = v
        self.inf = inf
        self.G = [[] for _ in range(v)]
        self.level = [0 for _ in range(v)]
        self.iter = [0 for _ in range(v)]

    def add_edge(self, from_, to, cap):
        # to: 行き先, cap: 容量, rev: 反対側の辺
        self.G[from_].append({'to':to, 'cap':cap, 'rev':len(self.G[to])})
        self.G[to].append({'to':from_, 'cap':0, 'rev':len(self.G[from_])-1})

    # sからの最短距離をbfsで計算
    def bfs(self, s):
        self.level = [-1 for _ in range(self.V)]
        self.level[s] = 0;
        que = queue.Queue()
        que.put(s)
        while not que.empty():
            v = que.get()
            for i in range(len(self.G[v])):
                e = self.G[v][i]
                if e['cap'] > 0 and self.level[e['to']] < 0:
                    self.level[e['to']] = self.level[v] + 1
                    que.put(e['to'])

    # 増加バスをdfsで探す
    def dfs(self, v, t, f):
        if v == t: return f
        for i in range(self.iter[v], len(self.G[v])):
            self.iter[v] = i
            e = self.G[v][i]
            if e['cap'] > 0 and self.level[v] < self.level[e['to']]:
                d = self.dfs(e['to'], t, min(f, e['cap']))
                if d > 0:
                    e['cap'] -= d
                    self.G[e['to']][e['rev']]['cap'] += d
                    return d

        return 0

    def max_flow(self, s, t):
        flow = 0
        while True:
            self.bfs(s)
            # bfsで到達不可
            if self.level[t] < 0 : return flow
            self.iter = [0 for _ in range(self.V)]
            f = self.dfs(s, t, self.inf)
            while f > 0:
                flow += f
                f = self.dfs(s,t, self.inf)