Ford-Fulkerson Algorithm
The Ford-Fulkerson Algorithm is a classical algorithm used to compute the maximum flow in a flow network. The algorithm was developed by L.R. Ford Jr. and D.R. Fulkerson in 1956. The idea behind the Ford-Fulkerson algorithm is simple: it repeatedly finds augmenting paths in the residual graph and increases the flow until no more augmenting paths can be found. This approach is key in solving maximum flow problems in various practical scenarios, such as network design, transportation, and resource allocation.
The algorithm is based on the flow network concept, where we have:
The maximum flow problem is to find the greatest amount of flow that can be sent from the source to the sink without exceeding the capacities of the edges.
The Ford-Fulkerson algorithm operates in the following steps:
The maximum flow is the total amount of flow from the source to the sink after no more augmenting paths can be found.
Let's walk through an example of how the Ford-Fulkerson algorithm works.
Consider the following flow network:
10
A ----------> B
| |
10 10
| |
v v
C ----------> D
10
The goal is to compute the maximum flow from source A to sink D.
We'll now look at how to implement the Ford-Fulkerson algorithm using Depth-First Search (DFS) for finding augmenting paths.
# Python program to implement Ford-Fulkerson algorithm using DFS
class Graph:
def __init__(self, vertices):
self.V = vertices # Number of vertices
self.graph = [[0] * vertices for _ in range(vertices)] # Capacity matrix
def add_edge(self, u, v, capacity):
self.graph[u][v] = capacity
def dfs(self, s, t, parent):
visited = [False] * self.V
stack = [s]
visited[s] = True
while stack:
u = stack.pop()
for v in range(self.V):
if not visited[v] and self.graph[u][v] > 0:
stack.append(v)
visited[v] = True
parent[v] = u
return visited[t]
def ford_fulkerson(self, source, sink):
parent = [-1] * self.V # Store the path
max_flow = 0
while self.dfs(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
# Update residual capacities
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
# Sample usage
graph = Graph(4)
graph.add_edge(0, 1, 10)
graph.add_edge(0, 2, 10)
graph.add_edge(1, 2, 5)
graph.add_edge(1, 3, 10)
graph.add_edge(2, 3, 10)
source = 0 # Source node
sink = 3 # Sink node
print(f"The maximum possible flow is {graph.ford_fulkerson(source, sink)}")
Explanation:
Graph class represents a flow network with V vertices.add_edge function adds edges with their capacities.dfs function is used to find augmenting paths in the residual graph.ford_fulkerson function calculates the maximum flow from the source to the sink using DFS to find augmenting paths and updating the residual graph.In this example, the flow from node A (0) to node D (3) is calculated, resulting in the maximum flow.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
class Graph {
public:
int V;
vector<vector<int>> graph;
Graph(int V) {
this->V = V;
graph.resize(V, vector<int>(V, 0));
}
void addEdge(int u, int v, int capacity) {
graph[u][v] = capacity;
}
bool dfs(int s, int t, vector<int>& parent) {
vector<bool> visited(V, false);
visited[s] = true;
parent[s] = -1;
vector<int> stack = {s};
while (!stack.empty()) {
int u = stack.back();
stack.pop_back();
for (int v = 0; v < V; ++v) {
if (!visited[v] && graph[u][v] > 0) {
stack.push_back(v);
visited[v] = true;
parent[v] = u;
}
}
}
return visited[t];
}
int fordFulkerson(int source, int sink) {
vector<int> parent(V);
int maxFlow = 0;
while (dfs(source, sink, parent)) {
int pathFlow = INT_MAX;
for (int v = sink; v != source; v = parent[v]) {
int u = parent[v];
pathFlow = min(pathFlow, graph[u][v]);
}
maxFlow += pathFlow;
for (int v = sink; v != source; v = parent[v]) {
int u = parent[v];
graph[u][v] -= pathFlow;
graph[v][u] += pathFlow;
}
}
return maxFlow;
}
};
int main() {
Graph g(4);
g.addEdge(0, 1, 10);
g.addEdge(0, 2, 10);
g.addEdge(1, 2, 5);
g.addEdge(1, 3, 10);
g.addEdge(2, 3, 10);
int source = 0;
int sink = 3;
cout << "The maximum possible flow is " << g.fordFulkerson(source, sink) << endl;
return 0;
}
Explanation:
dfs function finds augmenting paths.fordFulkerson function calculates the maximum flow and updates the residual graph.