![]() | ||
The Ford–Fulkerson method or Ford–Fulkerson algorithm (FFA) is a greedy algorithm that computes the maximum flow in a flow network. It is called a "method" instead of an "algorithm" as the approach to finding augmenting paths in a residual graph is not fully specified or it is specified in several implementations with different running times. It was published in 1956 by L. R. Ford, Jr. and D. R. Fulkerson. The name "Ford–Fulkerson" is often also used for the Edmonds–Karp algorithm, which is a specialization of Ford–Fulkerson.
Contents
The idea behind the algorithm is as follows: as long as there is a path from the source (start node) to the sink (end node), with available capacity on all edges in the path, we send flow along one of the paths. Then we find another path, and so on. A path with available capacity is called an augmenting path.
Algorithm
Let
This means that the flow through the network is a legal flow after each round in the algorithm. We define the residual network
Algorithm Ford–Fulkerson
Inputs Given a Network-
f ( u , v ) ← 0 for all edges( u , v ) - While there is a path
p froms tot inG f c f ( u , v ) > 0 for all edges( u , v ) ∈ p :- Find
c f ( p ) = min { c f ( u , v ) : ( u , v ) ∈ p } - For each edge
( u , v ) ∈ p -
f ( u , v ) ← f ( u , v ) + c f ( p ) (Send flow along the path) -
f ( v , u ) ← f ( v , u ) − c f ( p ) (The flow might be "returned" later)
-
- Find
The path in step 2 can be found with for example a breadth-first search or a depth-first search in
When no more paths in step 2 can be found,
If the graph
Also, if a node
Complexity
By adding the flow augmenting path to the flow already established in the graph, the maximum flow will be reached when no more flow augmenting paths can be found in the graph. However, there is no certainty that this situation will ever be reached, so the best that can be guaranteed is that the answer will be correct if the algorithm terminates. In the case that the algorithm runs forever, the flow might not even converge towards the maximum flow. However, this situation only occurs with irrational flow values. When the capacities are integers, the runtime of Ford–Fulkerson is bounded by
A variation of the Ford–Fulkerson algorithm with guaranteed termination and a runtime independent of the maximum flow value is the Edmonds–Karp algorithm, which runs in
Integral example
The following example shows the first steps of Ford–Fulkerson in a flow network with 4 nodes, source
Notice how flow is "pushed back" from
Non-terminating example
Consider the flow network shown on the right, with source
Note that after step 1 as well as after step 5, the residual capacities of edges
- Python program for implementation of Ford Fulkerson algorithm
from collections import defaultdict
- This class represents a directed graph using adjacency matrix representation
class Graph:
def __init__(self,graph): self.graph = graph # residual graph self. ROW = len(graph) #self.COL = len(gr[0]) Returns true if there is a path from source 's' to sink 't' in residual graph. Also fills parent[] to store the path def BFS(self,s, t, parent): # Mark all the vertices as not visited visited =[False]*(self.ROW) # Create a queue for BFS queue=[] # Mark the source node as visited and enqueue it queue.append(s) visited[s] = True # Standard BFS Loop while queue: #Dequeue a vertex from queue and print it u = queue.pop(0) # 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 True if visited[t] else False # Returns the maximum flow from s to t in the given graph def FordFulkerson(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