Ford-Fulkerson算法（FFA）是一种
贪婪算法，用于计算流网络中的最大流量。 它被称为“
方法”而不是“算法”，因为在残差图中找到增广路径的方法没有完全指定，或者在具有不同运行时间的若干实现中指定。 它由L. R. Ford，Jr。和D. R. Fulkerson于1956年出版。 名称“Ford-Fulkerson”通常也用于Edmonds-Karp算法，该算法是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.
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