Ford-Fulkerson Algorithm
Description
The Ford-Fulkerson algorithm is a method for computing the maximum flow in a flow network. It works by finding augmenting paths through the residual graph and adding flow along these paths. The algorithm repeatedly finds augmenting paths and adds flow until no more augmenting paths can be found.
History
The algorithm was first published in 1956 by L. R. Ford, Jr. and D. R. Fulkerson. It was developed during their time at RAND Corporation, where they were working on Soviet railway traffic flow and trying to identify which routes would be most disruptive if blocked. The algorithm has since become a fundamental tool in network flow theory and has applications in transportation, telecommunications, and many other fields.
How It Works
The Ford-Fulkerson algorithm uses an iterative approach to find the maximum flow:
-
Initialization:
- Set initial flow to 0 for all edges
- Create initial residual graph equal to the original graph
- Finding Augmenting Path:
-
Flow Update:
- Find the minimum possible flow along the augmenting path
- Update flow in both original and residual graphs
-
Iteration:
- Repeat steps 2 and 3 until no more augmenting paths are found
- The sum of all augmenting flows is the maximum flow
Visualization
Current Step
Click Start to begin
Current Flow
0
Path Found
None
Implementation
from collections import defaultdict
class Graph:
def __init__(self, vertices):
self.V = vertices
self.graph = [[0] * vertices for _ in range(vertices)]
def bfs(self, s, t, parent):
visited = [False] * self.V
queue = []
queue.append(s)
visited[s] = True
while queue:
u = queue.pop(0)
for v in range(self.V):
if not visited[v] and self.graph[u][v] > 0:
queue.append(v)
visited[v] = True
parent[v] = u
return visited[t]
def ford_fulkerson(self, source, sink):
parent = [-1] * self.V
max_flow = 0
while self.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
# Example usage
if __name__ == "__main__":
g = Graph(6)
g.graph = [[0, 16, 13, 0, 0, 0],
[0, 0, 10, 12, 0, 0],
[0, 4, 0, 0, 14, 0],
[0, 0, 9, 0, 0, 20],
[0, 0, 0, 7, 0, 4],
[0, 0, 0, 0, 0, 0]]
source, sink = 0, 5
print(f"Maximum flow from source {source} to sink {sink}: "
f"{g.ford_fulkerson(source, sink)}")
#include <iostream>
#include <limits.h>
#include <queue>
#include <string.h>
using namespace std;
class Graph {
int V;
int **graph;
bool bfs(int s, int t, int parent[]) {
bool *visited = new bool[V];
memset(visited, 0, sizeof(bool) * V);
queue<int> q;
q.push(s);
visited[s] = true;
parent[s] = -1;
while (!q.empty()) {
int u = q.front();
q.pop();
for (int v = 0; v < V; v++) {
if (!visited[v] && graph[u][v] > 0) {
if (v == t) {
parent[v] = u;
delete[] visited;
return true;
}
q.push(v);
parent[v] = u;
visited[v] = true;
}
}
}
delete[] visited;
return false;
}
public:
Graph(int V) {
this->V = V;
graph = new int*[V];
for (int i = 0; i < V; i++) {
graph[i] = new int[V];
memset(graph[i], 0, sizeof(int) * V);
}
}
void addEdge(int u, int v, int w) {
graph[u][v] = w;
}
int fordFulkerson(int s, int t) {
int *parent = new int[V];
int max_flow = 0;
while (bfs(s, t, parent)) {
int path_flow = INT_MAX;
for (int v = t; v != s; v = parent[v]) {
int u = parent[v];
path_flow = min(path_flow, graph[u][v]);
}
for (int v = t; v != s; v = parent[v]) {
int u = parent[v];
graph[u][v] -= path_flow;
graph[v][u] += path_flow;
}
max_flow += path_flow;
}
delete[] parent;
return max_flow;
}
~Graph() {
for (int i = 0; i < V; i++)
delete[] graph[i];
delete[] graph;
}
};
int main() {
Graph g(6);
g.addEdge(0, 1, 16);
g.addEdge(0, 2, 13);
g.addEdge(1, 2, 10);
g.addEdge(1, 3, 12);
g.addEdge(2, 1, 4);
g.addEdge(2, 4, 14);
g.addEdge(3, 2, 9);
g.addEdge(3, 5, 20);
g.addEdge(4, 3, 7);
g.addEdge(4, 5, 4);
cout << "Maximum flow: " << g.fordFulkerson(0, 5) << endl;
return 0;
}
public class Graph
{
private int V;
private int[,] graph;
public Graph(int vertices)
{
V = vertices;
graph = new int[V, V];
}
private bool BFS(int s, int t, int[] parent)
{
bool[] visited = new bool[V];
Queue<int> queue = new Queue<int>();
queue.Enqueue(s);
visited[s] = true;
parent[s] = -1;
while (queue.Count > 0)
{
int u = queue.Dequeue();
for (int v = 0; v < V; v++)
{
if (!visited[v] && graph[u, v] > 0)
{
queue.Enqueue(v);
parent[v] = u;
visited[v] = true;
}
}
}
return visited[t];
}
public int FordFulkerson(int source, int sink)
{
int[] parent = new int[V];
int maxFlow = 0;
while (BFS(source, sink, parent))
{
int pathFlow = int.MaxValue;
for (int v = sink; v != source; v = parent[v])
{
int u = parent[v];
pathFlow = Math.Min(pathFlow, graph[u, v]);
}
for (int v = sink; v != source; v = parent[v])
{
int u = parent[v];
graph[u, v] -= pathFlow;
graph[v, u] += pathFlow;
}
maxFlow += pathFlow;
}
return maxFlow;
}
public void AddEdge(int u, int v, int w)
{
graph[u, v] = w;
}
}
public class Program
{
public static void Main()
{
Graph g = new Graph(6);
g.AddEdge(0, 1, 16);
g.AddEdge(0, 2, 13);
g.AddEdge(1, 2, 10);
g.AddEdge(1, 3, 12);
g.AddEdge(2, 1, 4);
g.AddEdge(2, 4, 14);
g.AddEdge(3, 2, 9);
g.AddEdge(3, 5, 20);
g.AddEdge(4, 3, 7);
g.AddEdge(4, 5, 4);
Console.WriteLine($"Maximum flow: {g.FordFulkerson(0, 5)}");
}
}
Complexity Analysis
Time Complexity
The time complexity of Ford-Fulkerson algorithm is O(VE²), where V is the number of vertices and E is the number of edges. This can be broken down into:
-
BFS/DFS Search: O(V + E)
- Each search visits all vertices and edges once
- Used to find augmenting paths
-
Maximum Flow: O(E)
- Each augmenting path can increase flow by at least 1
- Maximum flow is bounded by O(E × maxCapacity)
-
Number of Iterations: O(VE)
- In worst case, each path augments flow by 1
- Total number of augmenting paths can be O(VE)
Space Complexity
The space complexity is O(V²), which includes:
-
Residual Graph: O(V²)
- Adjacency matrix representation
- Stores flow capacities between all pairs of vertices
-
Parent Array: O(V)
- Stores path information during BFS/DFS
-
Visited Array: O(V)
- Used in BFS/DFS to track visited vertices
Advantages and Disadvantages
Advantages
- Simple and intuitive implementation
- Works well with integer capacities
- Can be modified for different flow problems
- Provides both maximum flow and minimum cut
- Easy to understand and implement with BFS
Disadvantages
- May be slow for large networks
- Not optimal for real-valued capacities
- Time complexity depends on flow values
- Can be inefficient compared to push-relabel
- Memory intensive for dense graphs