[演算法] [Graph 圖] maximum flow 最大流量問題

這篇文章來討論有關 圖 的最大流量的問題。

題目大致會給一張圖,給出口和入口。求入口到出口的最大流量。

下面給一個狀況,來演示我解決這個問題所使用的方法。
如下圖:
每個圓圈代表一個節點,圓圈中的數字代表節點編號,
每個箭頭表示通道,箭頭中的數字表示通道流量,
有 6 個節點 0 ~ 5 ,有些節點之間有通道連接著,
每個通道在每個單位時間最多只能通過固定的人數,
節點 0 可以通往 節點 2節點 3
兩條通道每個單位時間最多能分別通過 4 人和 6 人...

----_20180220200248

現在 節點 0節點 1入口
節點 4節點 5出口
求從入口到出口每個單位時間最多能通過多少人?

如果從直接看這張一經畫成圖片的圖,會發現它的架構非常簡單,
沒有環路,看一看就可以算出答案。

我聽過一個方法:
他求出 節點 2 的總入流,和總出流求出,
取兩數最小值
再對 節點 3 做一樣的事
16 = min((4 + 5), (4 + 4)) + min((6 + 2), (6 + 6))
最後得到 16

對於這個方法,我只能說:
因為這張圖的特殊構造,
所以才可以使用這個方法求到答案。

我的作法

  1. 找出任意一條路線 P,從第 1 個入口到第 1 個出口
  2. 如果可以到,執行 步驟 4 5 6
  3. 如果找不到,回到 步驟 1到下一個出口 的路徑,再找不到回到 步驟 1 試下一個入口
  4. 求出這條路徑的流量 F 並記錄 (路徑中所有通道的最小值)
  5. 將整條路徑所有通道的最大流量減去 F ,如果通道流量剩餘 0 視為通道不存在
  6. 重複步驟 1
  7. 求出所有 F 的總和

示範

題目
----_20180220200248-1

找到一條路徑,並求出路徑流量 F (4)
將路徑上所有通道減去 F (4)
----_20180220232151

忽略流量為 0 的通道
----_20180220232206

找到另一條路徑,路徑流量為 6
----_20180220232217

忽略流量為 0 的通道
----_20180220232229

節點 0 已經到不了任何出口,換下一個節點出發
找到路徑,求出流量,通道減去流量
----_20180220232239

----_20180220232321

最後將所有路徑的流量相加
16 = 4 + 6 + 4 + 2
----_20180220232335

用 python 來完成,
假設輸入的格式長這樣,
然後要寫一個 answer(entrances, exits, path) 的 function ,回傳最大流量

entrances = [0, 1]
exits = [4, 5]
path = [
  [0, 0, 4, 6, 0, 0],  # Room 0: Entrance
  [0, 0, 5, 2, 0, 0],  # Room 1: Entrance
  [0, 0, 0, 0, 4, 4],  # Room 2: Intermediate node
  [0, 0, 0, 0, 6, 6],  # Room 3: Intermediate node
  [0, 0, 0, 0, 0, 0],  # Room 4: Exit
  [0, 0, 0, 0, 0, 0],  # Room 5: Exit
]

entrances 為所有的入口, exits 為所有的出口

from copy import deepcopy
from collections import deque


def answer(entrances, exits, path):
    graph = deepcopy(path)
    length = len(graph)
    max_flow = 0

    def bfs(s, t, parent):
        visited = [False] * length
        queue = deque()
        queue.append(s)
        visited[s] = True
        while queue:
            u = queue.popleft()
            for index, value in enumerate(graph[u]):
                if not visited[index] and value > 0:
                    queue.append(index)
                    visited[index] = True
                    parent[index] = u
        return visited[t]

    for source in entrances:
        for sink in exits:
            parent = [-1] * length
            while bfs(source, sink, parent):
                print(parent)
                path_flow = 2000000 # a large number
                s = sink
                while s != source:
                    path_flow = min(path_flow, graph[parent[s]][s])
                    s = parent[s]
                max_flow += path_flow
                v = sink
                while v != source:
                    u = parent[v]
                    graph[u][v] -= path_flow
                    # graph[v][u] += path_flow
                    v = parent[v]
    return max_flow


print(answer([0, 1], [4, 5], [
  [0, 0, 4, 6, 0, 0],  # Room 0: Entrance
  [0, 0, 5, 2, 0, 0],  # Room 1: Entrance
  [0, 0, 0, 0, 4, 4],  # Room 2: Intermediate node
  [0, 0, 0, 0, 6, 6],  # Room 3: Intermediate node
  [0, 0, 0, 0, 0, 0],  # Room 4: Exit
  [0, 0, 0, 0, 0, 0],  # Room 5: Exit
]))

print(answer([0], [3], [[0, 7, 0, 0], [0, 0, 6, 0], [0, 0, 0, 8], [9, 0, 0, 0]]))

其實我寫的這個題目來自 Google foobar ,
如果可以挑戰的話應該有可能可以遇到,
題目名稱叫 Escape Pods 。

當然我的方法不一定最好的,
歷史上也有很多對此問題做過研究的人,
也產生了需多種方法,像是:
Fold-Fulkerson algorithm
Edmonds-Karp algorithm
Dininc's algorithm
等等...

Show Comments