Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
What exactly is the maximum flow issue?
3.
Ford Fulkerson Technique
4.
Remaining Network
5.
Example
6.
Code implementation in java
6.1.
Output
7.
Code implementation in C++
7.1.
Output
8.
Complexity
8.1.
Time Complexity
8.2.
Space complexity
9.
Frequently Asked Questions
9.1.
What distinguishes Edmonds-Karp from Ford-Fulkerson? 
9.2.
What is the maximum flow algorithm?
9.3.
Give Ford-Fulkerson applications?
9.4.
Is the Floyd-Warshall algorithm greedy?
9.5.
What is an edge path?
10.
Conclusion
Last Updated: Mar 27, 2024
Medium

Ford-Fulkerson Algorithm for Maximum Flow

gp-icon
Data structures & algorithms (Beginner to Intermediate)
Free guided path
13 chapters
99+ problems
gp-badge
Earn badges and level up

Introduction

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.

Introduction

There is nothing to assist you, so don't worry. You may approach this as a maximum-flow problem and use the Ford Fulkerson technique to find a solution.

What exactly is the maximum flow issue?

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. 

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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.

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.

residual network

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.

Check Out the articles mentioned below.

If you face any doubt, please comment, and we will love to answer your questions.

Want expertise in Python for your next web development project? Check out our course.

Nevertheless, you may consider our paid courses to give your career an edge over others!

Do upvote our blogs if you find them helpful and engaging!

Happy Learning!

Guided path
Free
gridgp-icon
Data structures & algorithms (Beginner to Intermediate)
13 chapters
109+ Problems
gp-badge
Earn badges and level up
Live masterclass