1.
Introduction
2.
Problem Statement
2.1.
Sample Examples
3.
Approach
3.1.
Implementation in C++
3.1.1.
Time Complexity
3.1.2.
Space Complexity
4.
4.1.
What are graphs?
4.2.
What are cyclic and acyclic graphs?
4.3.
What are directed and undirected graphs?
5.
Conclusion
Last Updated: Mar 27, 2024
Hard

# Maximum number of edge-disjoint paths between two vertices

Harsh
0 upvote
Crack Google SDE interview : Essential projects
Speaker
Saurav Prateek
SDE-2 @
20 Jun, 2024 @ 01:30 PM

## Introduction

A non-linear data structure called a graph has vertices and edges. Broadly speaking, the graph is of two types: Directed and Undirected. Edges in directed graphs have a direction whereas edges in the undirected graph do not have any direction. The problem discussed in this blog uses a directed graph.

In this blog, we will discuss a graph theory problem in which we have to find the maximum number of edge-disjoint paths between two vertices.

## Problem Statement

Ninja has given you a directed graph and a Source and Destination vertex. Your task is to print the maximum number of edge-disjoint paths between source and destination vertex.

The edge-disjoint paths are the paths in which no edge is used more than once.

Example:

In the above figure, there are 3 paths between 0 and 3 but only path1 and path2 will be considered as edge-disjoint paths and not the path 3 because we can use any edge only once.

### Sample Examples

Input

Output

Maximum number of edge disjoint paths between 0 and 7: 2

Explanation

As explained in the problem statement. The edge-disjoint paths in the edge can be used only once. So, the total number of edge disjoint paths in our input graph is 2.

Both of the paths are shown in the below figure.

There is another path 0–>3–>4–>5–>7 but in this path we have to use the edge 5–>7 which is already used in path 1 as shown in the above figure. That is why the total maximum number of edge-disjoint paths is 2 and not 3 or 4.

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

## Approach

To fully understand the approach used to solve this problem. One needs to know about the Ford-Fulkerson method. The ford-Fulkerson method is a greedy algorithm that computes the maximum flow in a flow network.

Have a look at the article mentioned below to know more about ford-Fulkerson method.

Ford-Fulkerson Algorithm for Maximum Flow

The basic idea behind the approach is that if there exists a path between the source and destination vertex we find that path and add it to the total paths. Then we find another path and this process continues until all of the paths are not explored.

The idea behind the ford-Fulkerson algorithm:

2. While there is an augmenting path from source to destination.

1. Add this path to the total available paths.

This problem can be solved using the approach used in the maximum flow problem in which we use the ford-Fulkerson algorithm. To know more about the ford-fulkerson algorithm you can have a look at the article mentioned below:

``````Pseudocode
Get_Paths (Graph, src, dest):
int parent[total number of vertices] <- {0, 0,....., 0}
int total_paths = 0;

while (there exists a path between src and dest):
int path <- 0;

int v <- dest;
while v != src:
int u = parent[v];
path = Graph[u][v];
Graph[u][v] = 0;
END_WHILE

total_paths = total_paths + path;

END_WHILE

### Implementation in C++

``````#include <bits/stdc++.h>
using namespace std;

// function to check whether there exists a path between a source and destination
// vertex
bool pathExits(vector<vector<int>> graph, int src, int dest, vector<int> &parent){
// bool array to keep track of visited vertices
vector<bool> visited(graph.size(), false);

// queue for bfs
queue<int> q;

// pushing source vertex into our queue
q.push(src);

// marking source vertex as visited
visited[src] = true;
parent[src] = -1;

// bfs
while(!q.empty()){
int u = q.front();
q.pop();
for(int v = 0; v < graph.size(); v++){

// if there exist an edge between u and v
// and it's still not visited push it into the queue
if(!visited[v] && graph[u][v] == 1){
q.push(v);
parent[v] = u;
visited[v] = true;
}
}
}

// return true if we have visited the destination
// vertex, else it will return false;
return visited[dest];
}

int getPaths(vector<vector<int>> graph, int src, int dest){

vector<int> parent(graph.size());
int total_paths = 0;

while(pathExits(graph, src, dest, parent)){
int path = 0;
for(int v = dest; v != src; v = parent[v]){
// getting parent vertex
int u = parent[v];

// if there's an edge between u and v
// path will become 1
path = graph[u][v];

// removing the edge as we need edge disjoint paths
graph[u][v] = 0;
}

total_paths += path;
}

}

int main(){
vector<vector<int>> graph = {
{0, 1, 1, 1, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 1, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 1, 0, 0},
{0, 0, 0, 0, 1, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 1, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 1, 1, 0},
{0, 0, 0, 0, 0, 0, 0, 1, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0},
};
int src = 0;
int dest = 7;
cout << "Maximum number of edge disjoint paths between " << src << " and " << dest << ": " << getPaths(graph, src, dest) << endl;
return 0;
}``````

Output

``Maximum number of edge disjoint paths between 0 and 7: 2``

#### Time Complexity

The time complexity of the above program is O(EV^3), where E is the number of edges in our graph and V is the number of vertices. As we are using bfs to check whether the path exists between the source and destination vertex again and again that is why the time complexity of our program is O(EV^3).

#### Space Complexity

To implement a bfs we need to use a queue. So, the space complexity of our program is O(V), where V is the number of vertices in our program.

### What are graphs?

One common type of data structure is a graph, which consists of a finite number of nodes (also called vertices) and a finite number of connected edges. An edge is a pair (u, v) that denotes a connection between u and v vertices.

### What are cyclic and acyclic graphs?

If a network has a cycle—a continuous set of nodes without any repeating nodes or edges that connects back to itself—then it is said to be cyclic. Acyclic graphs are those without cycles.

### What are directed and undirected graphs?

Edges in directed graphs point from one end of the graph to the other. The edges in undirected networks merely link the nodes at each end.

## Conclusion

In this article, we have extensively discussed a problem related to graph theory in which we have to print the maximum number of edge-disjoint paths between two vertices. We have seen an implementation in which we are using the Ford-Fulkerson algorithm.

Recommended Problems:

If you think this blog has helped you enhance your knowledge about the above question, and if you would like to learn more, check out our articles

and many more on our website.

Visit our website to read more such blogs. Make sure that you enroll in the courses provided by us, take mock tests and solve problems and interview puzzles available. Also, you can pay attention to interview stuff- interview experiences and an interview bundle for placement preparations.

Please upvote our blog to help other ninjas grow.

Happy Learning!

Live masterclass