Ford-Fulkerson算法（FFA）是一種貪婪算法，用於計算流網路中的最大流量。 它被稱為“方法”而不是“算法”，因為在殘差圖中找到增廣路徑的方法沒有完全指定，或者在具有不同運行時間的若干實現中指定。 它由L. R. Ford，Jr。和D. R. Fulkerson於1956年出版。 名稱“Ford-Fulkerson”通常也用於Edmonds-Karp算法，該算法是Ford-Fulkerson方法的完全定義的實現。
算法背後的想法如下：只要存在從源（起始節點）到接收器（端節點）的路徑，在路徑中的所有邊緣上具有可用容量，我們就沿著其中一個路徑傳送流。 然後我們找到另一條路徑，依此類推。 具有可用容量的路徑稱為擴充路徑。
基本介紹
- 中文名：Ford–Fulkerson算法
- 所屬學科：計算機
- 算法類型：貪婪算法
通過將流量增加路徑添加到已建立的流量，當不再能夠找到流量增加路徑時，將達到最大流量。但是，無法確定是否會達到這種情況，因此可以保證的最佳方案是，如果算法終止，答案將是正確的。在算法永遠運行的情況下，流可能甚至不會收斂到最大流量。但是，這種情況只發生在不合理的流量值。當容量為整數時，Ford-Fulkerson的運行時間受O（E f）的限制（參見大O表示法），其中E是邊和f是最大流量。這是因為每個擴充路徑都可以在O（E））時間內找到並且將流量增加至少1 的整數量，其上限f 。
具有保證終止和獨立於最大流量值的運行時間的Ford-Fulkerson算法的變體是Edmonds-Karp算法，該算法在中運行O(VE2)時間。
import collections
#This class represents directed graph using adjacency matrixrepresentation
class Graph:
def __init__(self, graph):
self.graph = graph # residual graph
self.ROW = len(graph)
def BFS(self, s, t, parent):
'''
Returns true if there is a path from source 's' to sink 't' in
residual graph. Also fills parent[] to store the path
'''
# Mark all the vertices as not visited
visited = [False] * (self.ROW)
# Create a queue for BFS
queue = collections.deque()
# Mark the source node as visited and enqueue it
queue.append(s)
visited[s] = True
# Standard BFS Loop
while queue:
u = queue.popleft()
# Get all adjacent vertices's of the dequeued vertex u
# # If a adjacent has not been visited, then mark it
# # visited and enqueue it
for ind, val in enumerate(self.graph[u]):
if (visited[ind] == False) and (val > 0):
queue.append(ind)
visited[ind] = True
parent[ind] = u
# If we reached sink in BFS starting from source, then return # true, else false
return visited[t]
# Returns the maximum flow from s to t in the given graph
def EdmondsKarp(self, source, sink):
# This array is filled by BFS and to store path
parent = [-1] * (self.ROW)
max_flow = 0
# There is no flow initially
# Augment the flow while there is path from source to sink
while self.BFS(source, sink, parent):
# Find minimum residual capacity of the edges along the
# path filled by BFS. Or we can say find the maximum flow
# through the path found.
path_flow = float("Inf")
s = sink
while s != source:
path_flow = min(path_flow, self.graph[parent[s]][s])
s = parent[s]
# Add path flow to overall flow
max_flow += path_flow
# update residual capacities of the edges and reverse edges
# along the path
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
