[最大流問題]pythonで実装し、アルゴリズムの流れを丁寧に見る

アルゴリズムとデータ構造
記事内に広告が含まれています。
スポンサーリンク

本記事では、

  • 最大フローとは何か
  • 最大フローを求めるアルゴリズム
  • 簡単なグラフを例に、どのようにアルゴリズムが進んでいくかのデモ

の3点がわかるように解説していきます。

スポンサーリンク

最大フロー(最大流)とは何か

まずはフローの意味から解説します。

フロー(flow)は『流れ』を意味する英単語であり、この問題においては

頂点sから頂点tへ”移動するもの”

という意味で解釈できます。

“移動するもの”の例として、水の流れる量や物資の運搬量などが挙げられます。

“移動するもの”はグラフを自由に移動できる訳ではなく、各辺に通過できる量の上限が設定されています。この値を容量と呼び、各辺の容量以上は通過できないという制限がつけられています。

ちなみに、最大フロー問題では、各辺に “(フローの量)/(容量)” という形式で設定が書かれていることが多いです。

図1: 有向辺のスラッシュの上にある数字がフローの量、下が容量を意味している。この図では、フローが2, 容量が4であることを意味している。

以上を踏まえ、最大フロー(最大流)問題とは以下の問題と定義できます。

各辺の上限を越えずに、頂点sから頂点tへものを移動させる時の最大量はいくらか?

図2: 最大フロー問題の例. 始点0から終点3までの最大フローは2である。(経路0→2→3に流せるフローは1, 経路0→1→2→3に流せるフローは1である。したがって、最大フローは1+1=2となる。)

アルゴリズムの準備: 残余グラフについて

上記で述べた最大フロー(最大流)問題を解くためのアルゴリズムとして、フォード・ファルカーソン法が挙げられます。このアルゴリズムを理解するためには、残余グラフの概念を知っておくが重要です。

残余グラフ

残余グラフを一言で言うと、各辺(有向辺)に逆向きの辺を設置したグラフ のことを意味します。この逆向きの辺のことを逆辺と呼びます。

この残余グラフの重要な性質として、逆辺のフローは辺に流れるフローと同じ量になる という点です。

図3: 辺と逆辺の関係について。上の黒い矢印が辺で、下の青矢印が逆辺。辺にフロー2が流れているとき、逆辺にも2が設定されます。

初期状態では、全辺のフローが0のため、逆辺の容量も0に設定されています。そして、この辺に流したフローの量の分だけ、逆辺の容量も増加します。

残余グラフの実装コードについて

残余グラフには辺とその逆辺が重要であり、辺・逆辺を実装するコードが以下になります。

G = [[] for _ in range(V)] #隣接グラフ

#逆辺も考慮した辺の初期化
def add_edge(From, To, c):
    #len(G[v])は逆辺を取得するための手がかり
    G[From].append([To, c, len(G[To])]) #辺の追加(終点ノード, 容量, 逆辺のインデックス)
    G[To].append([From, 0, len(G[From]) - 1]) #逆辺の追加

From が始点、To が終点の辺です。これらを隣接グラフに追加する関数が add_edge() 関数です。

G[From] に追加されるリストのうち、第一項目は終点ノード、第二項目は容量、第三項目は逆辺を指定する番号です。

全ての要素は隣接グラフ G[From], G[To] に後ろから追加されていくため、appendする直前のG[From], G[To] の要素数が分かれば逆辺を特定可能です。

例として以下の隣接グラフを考えます。

G = [[[1, 2, 0]], [[0, 0, 0], [2, 1, 0]], [[1, 0, 1]]]

このうち、ノード0の要素をみてみます。

G[0][0] = [[1, 2, 0]]

これは、ノード0はノード1へ容量2の辺を持っており、この逆辺はG[1]の0番目の要素であることを意味しています。 G[1]の0番目 を確認すると、

G[1][0] = [0, 0, 0]

ノード1がノード0へ容量0の有向辺を持っており、この逆辺はG[0]の0番目の要素であることを意味しており、辺・逆辺の対応が取れていることがわかります。

図4: ノード0とノード1の辺・逆辺の関係の図。0→1に対応するのがG[0][0] = [[1, 2, 0]], この逆辺に対応するのが G[1][0] = [0, 0, 0] です。

最大フローを求めるアルゴリズムコード

これを踏まえて、最大フローを求めるアルゴリズムをpythonで実装します。

実装には、以下の4つの関数を作成します。

  • add_edge() : 辺と逆辺を設定
  • bfs(): 幅優先探索 (始点sから各ノードへの距離を計算)
  • dfs(): 深さ優先探索 (残余グラフ上でs-tパスの探索を実行)
  • get_maxflow(): s-tパスの最大フローを求める
#max_flow.py

from collections import deque

#逆辺も考慮した辺の初期化
def add_edge(u, v, c):
    #len(G[v])は何を意味してる?->逆辺を取得するための手がかり
    G[u].append([v, c, len(G[v])])
    G[v].append([u, 0, len(G[u]) - 1])

#sからの最短距離を計算する
def bfs(s):
    #D: sからの距離を管理
    D = [-1] * V
    D[s] = 0
    Q = deque()
    Q.append(s)
    while len(Q) > 0:
        v = Q.popleft()
        for next, capa, _ in G[v]:
            if capa > 0 and D[next] < 0:
                D[next] = D[v] + 1
                Q.append(next)
    return D


#増加パス: すでに存在するs-tパスと共有する辺は逆流を許して
#         新たに追加できるs-tパスのこと
#2頂点s-t間の辺連結度を求める
#深さ優先探索(v始点, tゴール, f流量, D距離リスト)
##seen[v]: vから出る辺のうち、チェックした個数
def dfs(v, t, f, seen, D):
    if v == t:
        return f
    
    #頂点vから出る(逆辺も含む)辺を全て探索
    while seen[v] < len(G[v]):
        next, capacity, rev = G[v][seen[v]]

        #流す余地があり、かつ始点から遠ざかる方向のノードであれば探索
        if capacity > 0 and D[v] < D[next]:
            #min(f,capacity)は、s-tパスのうち最小容量しか流すことができない
            #ため必要になる
            flow = dfs(next, t, min(f, capacity), seen, D)
            if flow > 0:
                G[v][seen[v]][1] -= flow #flow分流せる流量が減る
                G[next][rev][1] += flow #逆流分足される
                return flow
        #探索ノード数
        seen[v] += 1
    return 0


def calc_max_flow(s, t):
    flow = 0
    while True:
        D = bfs(s)
        if D[t] < 0:
            return flow
        #頂点vから出るパスのうち、チェックした個数を管理
        seen = [0] * V
        while True:
            f = dfs(s, t, 1e10, seen, D)
            
            if f == 0:
                break
            flow += f

if __name__=="__main__":
		V, E = map(int, input().split())
		G = [[] for _ in range(V)]
    for _ in range(E):
        u, v, c = map(int, input().split())
        add_edge(u, v, c)

    max_flow = calc_max_flow(0, V - 1) #始点0, 終点V-1ノードの最大フロー
    print(max_flow)

幅優先探索では始点sから各ノードへの距離を探索し、リスト D で管理します。

深さ優先探索(dfs)では、再帰関数を用いて始点sから終端tまでの経路を探索し、その経路に流すことができるフローの量を計算します。

# v: 今いるノード
# t: ゴールのノード
# f: 今まで流したフロー、
#seen: ノードvから出ているパスのうち、チェックした個数を管理するリスト
#D: 幅優先探索で得られた、始点sからの距離を管理するリスト

def dfs(v, t, f, seen, D):
    ...略...

以下のコードのように各辺・逆辺の容量を更新する部分が最大フロー問題に特有な部分です。

#s-tパスのフローが確定した後、容量を更新
if flow > 0:
    G[v][seen[v]][1] -= flow #flow分流せる流量が減る
    G[next][rev][1] += flow #逆流分足される
    return flow

アルゴリズムのデモ

図5: テストグラフ

図2のグラフを用いて、頂点0から頂点3への最大フローを求めてみます。わかりやすさのため、map() 関数は用いずに直接入力しています。

#max_flow.py

#...略...
if __name__=="__main__":
    V, E = 4, 4 #頂点数, 辺の本数
    G = [[] for _ in range(V)]
    es = [[0, 1, 2], [0, 2, 1], [1, 2, 1], [2, 3, 2]] #このグラフの辺のリスト
    for _ in range(E):
        u, v, c = map(int, input().split())
        add_edge(u, v, c)

    max_flow = calc_max_flow(0, V - 1) #始点0, 終点V-1ノードの最大フロー
    print(f"最大流は {max_flow}")
    
    #最大流は 2

このように最大流の問題を解くことができます。

アルゴリズムの動作の流れを一つ一つ可視化

次に上記のアルゴリズムを図5のテストグラフに適用し、プログラムの挙動を一つ一つ丁寧に見ていきます。このグラフを解くまでに、幅優先探索 bfs()関数 で距離リストの更新が 3回 行われます。

そこで、アルゴリズムの流れをbfs()関数の更新のタイミングで区切って見ていきます。

#図5の隣接グラフG
#G = [[[1, 2, 0], [2, 1, 0]], [[0, 0, 0], [2, 1, 1]], [[0, 0, 1], [1, 0, 1], [3, 2, 0]], [[2, 0, 2]]]
max_flow = calc_max_flow(0, 3) #始点0, 終点V-1ノードの最大フロー

幅優先探索 1回目の実行

#calc_max_flowの中(56行目)
while True:
    D = bfs(s)
    #D = [0,1,1,2]

1回目の幅優先探索で、始点0から各ノードへの距離を計算します。この距離リスト D を用いて深さ優先探索 dfs() を計算します。

まずは始点0からの探索を実行します。

f = dfs(v=0, t=3, f=1e10, seen=[0,0,0,0], D=[0,1,1,2])

始点0からの探索 1

37行目以下の while文 内を見ていきます。リストの深さは再帰関数の深さとします。

  • next, capacity, rev = 1,1,0 のとき: capacity >0 and D[0]<D[1]より、43行目のif文に入る
    • f = dfs(v=1, t=3, f=1, seen, D)を計算
      • next, capacity, rev = 0,0,0: D[v=1] $\nless$ D[next=0]より終了
      • next, capacity, rev = 2,1,1: D[v=1] $\nless$ D[next=2]より終了
    • ここで v=1 の探索は終了

ここまでの流れは、0→1->2の経路 (赤線) を探索したことになります。

図6-1: 赤線の経路を探索した.

始点0からの探索 2

再び37行目以下の while文 内を見ていきます。次は頂点2を探索します。リストの深さは再帰関数の深さとします。

  • next, capacity, rev = 2,1,0 のとき: capacity >0 and D[0]<D[2] より、43行目のif文に入る
    • f = dfs(v=2, t=3, f=1, seen, D)を計算
      • next, capacity, rev = 0,0,0: D[v=2] $\nless$ D[next=0] より終了
      • next, capacity, rev = 2,1,1: D[v=2] $\nless$ D[next=2]より終了
      • next, capacity, rev = 3,2,0: D[v=2] < D[next=3]より46行目に入る
        • f = dfs(v=3, t=3, f=1, seen, D) を計算(46行目)
          • v=t=3 より、flow=1 に確定
      • 経路2→3の辺・逆辺のフローを更新(48,49行目)
      • G[2][3][1] = 2 - 1 = 1 (辺のフローを更新)
      • G[3][2][1] = 1 (逆辺のフローを更新)
    • 経路0→2 の辺・逆辺のフローを更新(48,49行目)
    • G[0][2][1] = 1 - 1 = 0 (辺のフローを更新)
    • G[2][0][1] = 1 (逆辺のフローを更新)

ここまでの流れは 0→2→3 の経路を探索したことになります。(赤線)

図6-2: 赤線の経路を探索した.

これまでの結果、残余グラフは以下のように更新されました。

図6-3: 残余グラフ. 青が逆辺を意味している。他の辺にも逆辺は存在するが、容量が0のため無視しています。

幅優先探索 2回目の実行

図6-3に対して幅優先探索を実行します。

while True:
    D = bfs(s)
    #D = [0,1,2,3]

ノード0からノード2 までの辺はこれ以上フローを流せないため、直接通行することができません。それにより 0→1→2 を経由する必要があるため、 D[2]=2 となっています。

始点0からの探索を行います。

f = dfs(v=0, t=3, f=1e10, seen=[0,0,0,0], D=[0,1,2,3])

始点0からの探索 1

37行目以下の while文 内を見ていきます。リストの深さは再帰関数の深さとします。

  • next, capacity, rev = 1,1,0 のとき: capacity >0 and D[0]<D[1] より、43行目のif文に入る
    • f = dfs(v=1, t=3, f=1, seen, D)を計算
      • next, capacity, rev = 0,0,0: D[v=1] $\nless$ D[next=0] より終了
      • next, capacity, rev = 2,1,1: D[v=1] < D[next=2] より46行目に入る
        • f = dfs(v=2, t=3, f=1, seen, D)を計算(46行目)
          • next = 0: D[v=2] $\nless$ D[next=0] より終了
          • next = 1: D[v=2] $\nless$ D[next=1] より終了
          • next = 3: D[v=2] < D[next=3] より46行目に入る
            • f = dfs(v=3, t=3, f=1, seen, D)を計算(46行目)
            • v=t=3 より、flow=1 に確定
        • 経路2→3の辺・逆辺のフローを更新(48,49行目)
        • G[2][3][1] = 1 - 1 = 0 (辺のフローを更新)
        • G[3][2][1] = 1+1= 2 (逆辺のフローを更新)
    • 経路1→2 の辺・逆辺のフローを更新(48,49行目)
    • G[1][2][1] = 1 - 1 = 0 (辺のフローを更新)
    • G[2][1][1] = 1 (逆辺のフローを更新)
  • 経路0→1 の辺・逆辺のフローを更新(48,49行目)
  • G[0][1][1] = 2 - 1 = 0 (辺のフローを更新)
  • G[1][0][1] = 1 (逆辺のフローを更新)

これまでの流れは、以下の赤線の部分を探索したことを意味します。

図6-4: 赤線の部分を探索したことを意味します。

この結果、残余グラフは以下のように更新されました。

図6-5: 得られた残余グラフの結果

幅優先探索 3回目の実行

図6-5の残余グラフに対して幅優先探索を実行します。

while True:
    D = bfs(s)
    #D = [0,1,-1,-1]

終点ノード 3 到達できない(D[3]=-1) ため、ここで探索が終了します。到達できない理由は、頂点0→頂点1の辺以外、容量と同じ量のフローが通過済みであるためです。

まとめ

最大フロー問題についてのアルゴリズムを解説し、その挙動を簡単なグラフを用いて丁寧に追っていきました。ちなみに、最大流問題を解くアルゴリズムのことをフォードファルカーソン法と呼びます。

Ford-Fullkerson法による最大フローの値を求めるアルゴリズム | アルゴリズムロジック
アルゴリズム 最大フローを求めるアルゴリズム(Ford-Fullkerson法): フロー \(f\) を 0 としてはじめるソース(入口) からシンク(出口)までの増加可能経路...

今回紹介したコードは AIZU ONLINE JUDGE 6_A で正答になることを確認しています。

Aizu Online Judge

今回のアルゴリズムでは、グラフ探索に関する重要アルゴリズム(幅優先探索・深さ優先探索・残余グラフ)を組み合わせて解く必要があります。以下の書籍に詳細に書かれているので、理解が曖昧な方はぜひ確認してみてください。

参考図書

『プログラミングコンテストチャレンジブック [第2版] 問題解決のアルゴリズム活用力とコーディングテクニックを鍛える』, 秋葉拓哉、 岩田陽一、 北川宜稔, マイナビbooks, 2012年

『問題解決力を鍛える!アルゴリズムとデータ構造』, 大槻兼資・著 秋葉拓哉・監修, 講談社サイエンティフィク, 2020年

コメント