解析Ford-Fulkerson演算法並透過Python實現

Ford-Fulkerson演算法是貪心演算法，用於計算網路中的最大流量。其原理是找到剩餘容量為正的增廣路徑，只要找到增廣路徑，就可以繼續增加路徑和運算流量。直到增廣路徑不再存在，這時就能得出最大流量。

Ford-Fulkerson演算法的術語

剩餘容量：就是將容量減去流量，在Ford-Fulkerson演算法中剩餘容量是正數，才能繼續作為路徑。

殘差網路：是一個具有相同頂點和邊的網絡，使用殘差容量作為容量。

增廣路徑：是殘差圖中從來源點到接收點的路徑，最終容量為0。

Ford-Fulkerson演算法原理範例

可能概念不是很清晰，下面來看一個範例，流網路所有邊的初始流量均為0，並有對應的容量上限，設起始點為S，接收點為T。

路徑一，S-A-B-T路徑剩餘容量為8、9、2，最小值為2，因此路徑一的流量為2，這時網路圖的流量為2。

路徑二，S-D-C-T路徑剩餘容量為3、4、5，最小值為3，因此我們可以將流量增加3，這時網路的流量為5。

路徑三，S-A-B-D-C-T路徑剩餘容量為6、7、7、1、2，最小值為1，因此流量增加1，這時網路的流量為6。

至此，已經沒有為正數的剩餘容量，得到該流網路的最大流是6。

Python實作Ford-Fulkerson演算法

from collections import defaultdict

class Graph:

    def __init__(self, graph):
        self.graph = graph
        self. ROW = len(graph)

    def searching_algo_BFS(self, s, t, parent):

        visited = [False] * (self.ROW)
        queue = []

        queue.append(s)
        visited[s] = True

        while queue:

            u = queue.pop(0)

            for ind, val in enumerate(self.graph[u]):
                if visited[ind] == False and val > 0:
                    queue.append(ind)
                    visited[ind] = True
                    parent[ind] = u

        return True if visited[t] else False

    def ford_fulkerson(self, source, sink):
        parent = [-1] * (self.ROW)
        max_flow = 0

        while self.searching_algo_BFS(source, sink, parent):

            path_flow = float("Inf")
            s = sink
            while(s != source):
                path_flow = min(path_flow, self.graph[parent[s]][s])
                s = parent[s]

            max_flow += path_flow

            v = sink
            while(v != source):
                u = parent[v]
                self.graph[u][v] -= path_flow
                self.graph[v][u] += path_flow
                v = parent[v]

        return max_flow

graph = [[0, 8, 0, 0, 3, 0],
         [0, 0, 9, 0, 0, 0],
         [0, 0, 0, 0, 7, 2],
         [0, 0, 0, 0, 0, 5],
         [0, 0, 7, 4, 0, 0],
         [0, 0, 0, 0, 0, 0]]

g = Graph(graph)

source = 0
sink = 5

print("Max Flow: %d " % g.ford_fulkerson(source, sink))

以上是解析Ford-Fulkerson演算法並透過Python實現的詳細內容。更多資訊請關注PHP中文網其他相關文章！