Hello Ninja, welcome back. Imagine being assigned the duty of creating a practical way to make daily airline timetables for thousands of flights. Numerous variables, such as the use of equipment, personnel distribution, customer satisfaction, variable weather conditions, breakdowns, etc., may need to be considered.
How quickly may material be transported (shipped) from the source to the sink while adhering to capacity restrictions?
In the maximum flow problem, given a flow network G, the goal is to find the biggest value flow from source s to sink t. Essentially, the flow network G=(V, E) is a directed graph with nonnegative flow capacity at each edge.
Ford Fulkerson Technique
The Ford Fulkerson technique commonly referred to as the "augmenting route algorithm," is a useful solution to the maximum flow issue. The Ford Fulkerson technique is based on two key ideas, which are as follows:
Residual Network.
Augmenting paths.
Here we will learn about Residual Network
Remaining Network
It is a graph with one or two edges for each edge in the original network and shares the same vertices as the original network. Additionally, it shows the potential increase in network flow. We'll figure out the extra flow for each edge as follows.
Additional flow equals the edge's capacity minus the edge's flow
So, using our original network, we will update each edge's capacity with the extra flow specific to that edge in order to establish a residual network. The quantity of flow currently passing through the edges of the original network will then be indicated by the addition of reverse edges.
Example
Let's examine the following example to help make this more understandable.
In the aforementioned example, the first number for each edge stands for the edge's capacity, and the second value for its flow value.
E.g. Let's think about the C->D edge. Here, the flow is 11, and the edge's capacity is 14. We obtain 14-11 = 3 when we compute the extra flow for this edge. Therefore, in the residual network, we may change the C->D edge's capacity to 3 and then create a reverse edge between C and D with a value of 11 (the original network's flow value).
Similarly, if we repeat this process for each edge, we get the residual network shown below.
Code implementation in java
// Ford-Fulkerson Maximum Flow Algorithm
import java.util.LinkedList;
class Ford_Fulkerson {
static final int V = 6;
// the use of BFS as a search algorithm
boolean bfs(int array_Graph[][], int s, int t, int p[]) {
boolean visited[] = new boolean[V];
for (int i = 0; i<V; ++i)
visited[i] = false;
LinkedList<Integer> queue = new LinkedList<Integer> ();
queue.add(s);
visited[s] = true;
p[s] = -1;
while (queue.size() != 0) {
int u = queue.poll();
for (int v = 0; v<V; v++) {
if (visited[v] == false && array_Graph[u][v] > 0) {
queue.add(v);
p[v] = u;
visited[v] = true;
}
}
}
return (visited[t] == true);
}
// Ford_Fulkerson algorithm use
int Ford_Fulkerson(int another_arr_graph[][], int s, int t) {
int u, v;
int array_Graph[][] = new int[V][V];
for (u = 0; u<V; u++)
for (v = 0; v<V; v++)
array_Graph[u][v] = another_arr_graph[u][v];
int p[] = new int[V];
int max_flow = 0;
// updating the edges' residual calues
while (bfs(array_Graph, s, t, p)) {
int all_path_flow = Integer.MAX_VALUE;
for (v = t; v != s; v = p[v]) {
u = p[v];
all_path_flow = Math.min(all_path_flow, array_Graph[u][v]);
}
for (v = t; v != s; v = p[v]) {
u = p[v];
array_Graph[u][v] -= all_path_flow;
array_Graph[v][u] += all_path_flow;
}
// The route flows when added
max_flow += all_path_flow;
}
return max_flow;
}
public static void main(String[] args) throws java.lang.Exception {
int another_arr_graph[][] = new int[][] {
{
0, 8, 0, 0, 3, 0
}, {
0, 0, 9, 0, 0, 0
}, {
0, 0, 0, 0, 7, 2
}, {
0, 0, 0, 0, 0, 5
}, {
0, 0, 7, 4, 0, 0
}, {
0, 0, 0, 0, 0, 0
}
};
Ford_Fulkerson m = new Ford_Fulkerson();
System.out.println("Maximum Flow: " + m.Ford_Fulkerson(another_arr_graph, 0, 5));
}
}
Output
Maximum Flow: 6
Code implementation in C++
// Ford-Fulkerson Maximum Flow Algorithm
#include <limits.h>
#include <string.h>
#include <iostream>
#include <queue>
using namespace std;
#define V 6
// the use of BFS as a search algorithm
bool breadth_first_search(int arr_graphr[V][V], int s, int t, int arr_parent[])
{
bool arr_visited[V];
memset(arr_visited, 0, sizeof(arr_visited));
queue<int> q;
q.push(s);
arr_visited[s] = true;
arr_parent[s] = -1;
while (!q.empty())
{
int u = q.front();
q.pop();
for (int v = 0; v < V; v++)
{
if (arr_visited[v] == false &&
arr_graphr[u][v] > 0)
{
q.push(v);
arr_parent[v] = u;
arr_visited[v] = true;
}
}
}
return (arr_visited[t] == true);
}
// Ford_Fulkerson algorithm use
int fordFulkerson(int graph[V][V], int s, int t)
{
int u, v;
int arr_graphr[V][V];
for (u = 0; u < V; u++)
for (v = 0; v < V; v++) arr_graphr[u][v] = graph[u][v];
int arr_parent[V];
int max_flow = 0;
// updating the edges' residual values
while (breadth_first_search(arr_graphr, s, t, arr_parent))
{
int all_path_flow = INT_MAX;
for (v = t; v != s; v = arr_parent[v])
{
u = arr_parent[v];
all_path_flow =
min(all_path_flow, arr_graphr[u][v]);
}
for (v = t; v != s; v = arr_parent[v])
{
u = arr_parent[v];
arr_graphr[u][v] -= all_path_flow;
arr_graphr[v][u] += all_path_flow;
}
// The route flows when added
max_flow += all_path_flow;
}
return max_flow;
}
int main()
{
int graph[V][V] = {
{0, 8, 0, 0, 3, 0},
{0, 0, 9, 0, 0, 0},
{0, 0, 0, 0, 7, 2},
{0, 0, 0, 0, 0, 5},
{0, 0, 7, 4, 0, 0},
{0, 0, 0, 0, 0, 0}
};
cout << "Max Flow: " << fordFulkerson(graph, 0, 5) << endl;
}
Output
Maximum Flow: 6
Complexity
Time Complexity
O(V*E^2): where V is the number of vertexes and E is the Edges.
Reason: Implement the Ford-Fulkerson Method in O(E) at each iteration. The worst-case temporal complexity as we utilize BFS to discover augmenting route (Edmonds-Karp implementation) is O(V * E ^ 2).
Space complexity
O(V+E): where V is the number of vertexes and E is the Edges.
Reason: We use E space for each vertex in the worst-case scenario. Hence the complexity of O(V+E).
Frequently Asked Questions
What distinguishes Edmonds-Karp from Ford-Fulkerson?
In contrast to Ford-Fulkerson, Edmonds-Karp uses a breadth-first search to determine the next augmenting path (bfs). The shortest augmenting path from the source to the sink will be selected by Edmonds-Karp if there are numerous augmenting pathways to choose from.
What is the maximum flow algorithm?
It is described as the highest flow rate that the network will let go from source to sink. The maximum flow problem may be solved using a variety of techniques. The Ford-Fulkerson method and Dinic's Algorithm are two popular algorithms for solving this type of issue.
Give Ford-Fulkerson applications?
While the Edmonds-Karp method and the Goldberg-Tarjan algorithm employ breadth-first searches and are done from the sink, labeling each vertex with the distance to the sink, the Ford-Fulkerson approach may be used to determine the highest flow between a single source and a single sink in a graph.
Is the Floyd-Warshall algorithm greedy?
While the greedy algorithm evaluates each node passed to pick the shortest route (Local Optimum) so that the time needed for searching is faster, the Floyd-Warshall algorithm considers all potential routes so that some ways are presented. So it is regarded as a greedy algorithm.
What is an edge path?
A path in a network is a finite or infinite sequence of edges connecting a series of vertices that, by most definitions, are all distinct (and since the vertices are different, so are the edges).
Conclusion
This post taught us how to determine maximum flows using the Ford Fulkerson approach. The maximum flow issue has several applications, including bipartite graphs, baseball elimination, and airline scheduling, among others. This is a crucial algorithm that will improve your competitive coding abilities and maybe prepare you for your interview.
81+ registered 