Last Updated: 5 Nov, 2021

Maximum Flow

Ninja

Asked in companies

Solve now

Problem statement

There are ‘N’ houses in the Ninja Land, numbered from 1 to N. You are given M pipes connecting the houses. ‘PIPES[i]’ is represented as [FROM, TO, CAPACITY]. Your task is to find the maximum flow of water from house 1 to house N,

For Example:

You are given ‘N’ = 4, ‘M’ = 3 and ‘PIPES’ = [[1, 2, 2], [1, 3, 4], [3, 4, 3]]. The maximum flow will be 3. The graph will look like this:

graph0

The maximum flow will be 3 because 4 units of water can flow from 1 -> 3, and 3 units of water can flow from 3 -> 4.

Input Format :

The first line of the input contains a single integer 'T', representing the number of test cases.

The first line of each test case contains two space-separated integers, ‘N’ and ‘M’, representing the numbers of houses and pipes, respectively.

The next line ‘M’ lines contain three space-separated integers representing a pipe.

Output Format:

For each test case, print the maximum flow of water from house 1 to house N.

Print the output of each test case in a separate line.

Note:

You do not need to print anything. It has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 10
1 <= N <= 500
1 <= M <= (N*(N-1))/2
1 <= PIPES[i][0] <= N
1 <= PIPES[i][1] <= N
1 <= PIPES[i][2] <= 500

Time Limit: 1 sec

Solve now

Approaches

01 Approach

Prerequisite: Ford-Fulkerson algorithm.

We will use the Ford-Fulkerson algorithm to find the maximum flow. It is a greedy algorithm that computes the maximum flow in a flow network.

The basic idea behind the Ford-Fulkerson algorithm is that 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 with one of the paths. Then we find another path, and so on.

Terminologies:

Residual capacity: Capacity of an edge after subtracting the flow from the maximum capacity.
Residual graph: Original graph with residual capacity instead of given capacities.
Augmenting path: A path with available capacity.

To check whether a path exists from the source to the sink, we will use BFS. BFS is a traversing algorithm where you should start traversing from a start node and traverse the graphs layer-wise. We will use the ‘VISITED’ array to keep track of all the visited nodes, and if VISITED[SINK] is true, there is a path from the source to the sink.

Algorithm :

Initialize a 2D array 'GRAPH' to represent the graph.
Iterate 'PIPE' in 'PIPES' to create graph:
- Initialize a variable 'FROM' with value 'PIPE.GET(0)'.
- Initialize a variable 'TO' with value 'PIPE.GET(1)'.
- Initialize a variable 'WEIGHT' with value 'PIPE.GET(2)'.
- Set 'GRAPH[FROM][TO]' as ('GRAPH[FROM][TO]' + 'WEIGHT').
- Set 'GRAPH[TO][FROM]' as ('GRAPH[TO][FROM]' + 'WEIGHT').
Initialize a variable 'MAXFLOW' to store maximum flow.
Set 'MAXFLOW' as 'FORDFULKERSON(1, 'N', 'GRAPH')'.
Return 'MAXFLOW'.

Maintain a function ‘FORDFULKERSON(INT SOURCE, INT SINK, INT[][] GRAPH)’:

Initialize a 2D array 'RESIDUALGRAPH' to represent the residual graph.
Iterate 'I' in 0 to 'GRAPH.LENGTH':
- Iterate 'J' in 0 to 'GRAPH.LENGTH':
  - Set 'RESIDUALGRAPH'['I']['J'] as 'GRAPH'['I']['J'].
Initialize an integer array 'PARENT'.
Initialize a variable 'MAXFLOW' with value 0.
Iterate while there exists a path between 'SOURCE' and 'SINK' in 'RESIDUALGRAPH':
- Initialize a variable 'CAPACITY' with value 1000000000.
- Initialize a variable 'T' with the value 'SINK'.
- Iterate while 'T' is not equal to 'SOURCE':
  - Initialize a variable 'S' with value 'PARENT['T']'.
  - Set 'CAPACITY' as the minimum of 'CAPACITY' and 'RESIDUALGRAPH['S']['T']'.
  - Set 'T' as 'S'.
- Set 'T' as 'SINK'.
- Iterate while 'T' is not equal to 'SOURCE':
  - Initialize a variable 'S' with value 'PARENT['T']'.
  - Set 'RESIDUALGRAPH['S']['T']' AS ('RESIDUALGRAPH'['S']['T'] - 'CAPACITY').
  - Set 'T' as 'S'.
- Set 'MAXFLOW' as ('MAXFLOW' + 'CAPACITY').
Return 'MAXFLOW'.

Maintain a function ‘BFS(INT[][] RESIDUALGRAPH, INT SRC, INT DEST, INT[] PARENT)’:

Initialize a boolean array 'VISITED'.
Intialize a Queue 'QUEUE'.
Add 'SRC' to 'QUEUE'.
Set 'PARENT['SRC']' as -1.
Set 'VISITED['SRC']' as true.
Iterate while 'QUEUE' is not empty:
- Initialize a variable 'U' with value 'QUEUE.POLL()'.
- Iterate 'V' in 0 to 'PARENT.LENGTH':
- If 'VISITED['V']' is false and 'RESIDUALGRAPH['U']['V']' is greater then 0.
  - Add 'V' to 'QUEUE'.
  - Set 'PARENT['V']' as 'U'.
  - Set 'VISITED['V']' as true.
Return 'VISITED'['DEST']'.

Solve now