Ford-Fulkerson算法（FFA）是一種貪婪算法，用於計算流網路中的最大流量。 它被稱為“方法”而不是“算法”，因為在殘差圖中找到增廣路徑的方法沒有完全指定，或者在具有不同運行時間的若干實現中指定。 它由L. R. Ford，Jr。和D. R. Fulkerson於1956年出版。 名稱“Ford-Fulkerson”通常也用於Edmonds-Karp算法，該算法是Ford-Fulkerson方法的完全定義的實現。
算法背後的想法如下：只要存在從源（起始節點）到接收器（端節點）的路徑，在路徑中的所有邊緣上具有可用容量，我們就沿著其中一個路徑傳送流。 然後我們找到另一條路徑，依此類推。 具有可用容量的路徑稱為擴充路徑。
複雜,Edmonds-Karp算法的Python實現,
複雜
通過將流量增加路徑添加到已在圖中建立的流量，當在圖表中不再能夠找到流量增加路徑時，將達到最大流量。但是，無法確定是否會達到這種情況，因此可以保證的最佳方案是，如果算法終止，答案將是正確的。在算法永遠運行的情況下，流可能甚至不會收斂到最大流量。但是，這種情況只發生在不合理的流量值。當容量為整數時，Ford-Fulkerson的運行時間受O（E f）的限制（參見大O表示法），其中E是數字圖中的邊和f是圖中的最大流量。這是因為每個擴充路徑都可以在O（E））時間內找到並且將流量增加至少1 的整數量，其上限f 。
具有保證終止和獨立於最大流量值的運行時間的Ford-Fulkerson算法的變體是Edmonds-Karp算法，該算法在中運行O(VE2)時間。
Edmonds-Karp算法的Python實現
import collections # This class represents a directed graph using adjacency matrix representationclass 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