1.
Introduction
1.1.
Prerequisites
1.2.
Problem Statement
1.3.
Example
2.
Brute Force Approach
2.1.
Pseudocode
2.2.
Implementation (C++ Code)
2.2.1.
Complexity Analysis
3.
Optimized Approach
3.1.
Pseudocode
3.2.
Implementation (C++ Code)
3.2.1.
Complexity Analysis
4.
4.1.
Why is BFS(or Breadth-First Search) used for the shortest path?
4.2.
What is Queue?
4.3.
What is Multi Source Breadth First search?
5.
Conclusion
Last Updated: Mar 27, 2024

# Multi Source Shortest Path in Unweighted Graph

Anju Jaiswal
0 upvote
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

## Introduction

We'll look at how to find the Multi Source Shortest Path in an Unweighted Graph in this blog. Getting a firm grasp on graph-based algorithms and their applications is a critical problem that has been raised in numerous interviews.

### Prerequisites

Knowledge of graphs and related terminologies such as recursionstacksqueuestrees, and the two main algorithms DFS AlgorithmBFS, and topological sorting are common prerequisites for every graph problem. It is not advisable to proceed to the shortest path issues in graphs without mastering these fundamental methods and data structures.

Nonetheless, we'll try to go through every detail needed to discover the Multi Source Shortest Path in an Unweighted Graph.

Also check Application of graph data structure

### Problem Statement

What do we mean by the  Multi Source Shortest Path in an unweighted graph?

Let G = (V, E) be an unweighted graph with E edges and V vertices. There are S vertices, and we have to find the distance of each vertex from one of the nearest S vertices.

Let's look at an example first.

### Example

Given an Unweighted Graph G

Input :

``````Number of Vertices = 6
Number of Edges = 9
Sources: 3, 5
Edges:
1 2
1 5
2 3
3 4
3 6
4 5
4 6``````

Output :

``````Multi Source Shortest Path in Unweighted Graph
1 1
2 1
3 0
4 1
5 0
6 1``````

## Brute Force Approach

To find the closest source, we can loop through the vertices and perform a BFS (Breadth-First Search) from each vertex.

### Pseudocode

1. Initialize an array source that will be 1 at an index that is the source vertex; otherwise, 0.
1. We will run a loop to all the vertices, call BFS for each vertex, and pass it as an src variable.
2. The BFS function then will find the distance between the src variables and all other vertices and store it in an array dist.

1. At last, we run a loop, find the shortest distance between the src variable and multiple sources, and print it.
1. Then repeat the same procedure.

### Implementation (C++ Code)

``````#include <bits/stdc++.h>
using namespace std;
// The BFS function
void BFS(vector<int> adj[],int n, int src,int source[])

{
int dist[n];
for(int i = 0;i<n;i++) dist[i] = INT_MAX;
queue<int>  q;

dist[src] = 0;
q.push(src);

while(q.empty()==false)
{
int node = q.front();
q.pop();

if(dist[node] + 1 < dist[it]){
dist[it]=dist[node]+1;
q.push(it);
}
}
}
int m=INT_MAX;

for(int i = 0;i<n;i++){
if(source[i]){
m = min(dist[i],m);
}
}
cout<< src<<" "<<m<<endl;

}
// This function calculates the distance of each
// vertex from nearest source
void Multi_source_shortest_path(vector<int> graph[], int n,
int sources[], int S){
int source[n];

// reseting the source hash array
for (int i = 1; i <= n; i++)
source[i] = 0;
for (int i = 0; i <= S - 1; i++)
source[sources[i]] = 1;
// loop through all the vertices and run
// a BFS from each vertex to find the distance
// to nearest town from it
for (int i = 1; i <= n; i++) {
BFS(graph, n,i,source);
}
}
{
}
// Driver Code
int main()
{ // Number of vertices
int n = 6;
// Edges
// Sources
int sources[] = { 3, 5 };
int S = sizeof(sources) / sizeof(sources[0]);
cout<<" Multi Source Shortest Path in Unweighted Graph "<<endl;
return 0;
}``````

Output

``````Multi Source Shortest Path in Unweighted Graph
1 1
2 1
3 0
4 1
5 0
6 1``````

#### Complexity Analysis

Time Complexity: O(V.(V+E))

We run a loop through the vertices, and from each vertex, run a BFS to find the closest source vertex. This will take O(V.E).

Space Complexity: O(V)

We are using a dist array to store the distance of each vertex from its nearest source and a queue whose space is the same as the number of vertices.

Read More - Time Complexity of Sorting Algorithms

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

## Optimized Approach

Multisource BFS, a variation of BFS, is an even better option.

### Pseudocode

1. We will queue all source vertices first rather than a single vertex as typical BFS.
2. Multisource BFS will visit all of the source vertices first in this manner. After that, it will go to the vertices that are 1 vertex away from all source vertices, then 2 vertices away from all source vertices, and so on.

### Implementation (C++ Code)

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

// Multisource BFS Function
, int dist[])
{
while(!q.empty())
{
int k = q.front();
q.pop();

{
{

// Pushing the adjacent unvisited vertices
// with distance from current source = this
// vertex's distance + 1
dist[i] = dist[k] + 1;
}
}
}
}

// This function calculates the distance of each
// vertex from nearest source
void  Multi_source_shortest_path(vector<int> graph[],int n,int sources[],int s)
{
//Create a queue for BFS
queue<int> q;
bool visited[n];
int dist[n];
for(int i = 0;i < n; i++){
dist[i] = 0;
}
//Mark all the source vertices as visited and enqueue it
for(int i = 0;i < s; i++)
{
q.push(sources[i]);
visited[sources[i]]=true;
}

Multisource_BFS(graph,q,n,visited,dist);

//Printing the distances
for(int i = 1; i <= n; i++)
{
cout<< i << " " << dist[i] << endl;
}

}
void addEdge(vector<int> graph[], int u, int v)
{
//Function to add 2 edges in an undirected graph
graph[u].push_back(v);
graph[v].push_back(u);
}

// Driver code
int main()
{
int n = 6;
// Edges
// Sources
int sources[] = { 3, 5 };
int S = sizeof(sources) / sizeof(sources[0]);
cout<<"Multi Source Shortest Path in Unweighted Graph "<<endl;
return 0;

}``````

Output

``````Multi Source Shortest Path in Unweighted Graph
1 1
2 1
3 0
4 1
5 0
6 1
``````

#### Complexity Analysis

Time Complexity: O(V+E)

In a single loop, we first enque all the source vertices. Multisource BFS will visit all of the source vertices first in this manner. After that, it will go to the vertices that are 1 vertex away from all source vertices, then 2 vertices away from all source vertices, and so on.

Space Space: O(V)

The array distance, boolean array to mark visited vertices, and the queue has used extra space.

#### Why is BFS(or Breadth-First Search) used for the shortest path?

If we wish to discover the shortest path in an undirected, unweighted graph, we utilize the BFS algorithm. The claim for BFS is that when a node is discovered for the first time during the traversal, its distance from the source will offer us the shortest path.

#### What is Queue?

A queue is a linear structure in which operations are carried out in a specific order. The order is First In, First Out (FIFO).

#### What is Multi Source Breadth First search?

A multiple-source BFS works in the same way as a standard BFS, except that instead of starting with a single node, you place all of your sources (A's) in the queue at the start. Put another way, perform a sweep across the grid to discover all A's and start your BFS queue with them at a distance of 0.

## Conclusion

We've addressed first, the method for finding the Multi-Source Shortest Path in an Unweighted Graph was discussed with an example.Then we discussed about how to implement the strategy to solve the problem.

Check out this problem - Root To Leaf Path

Refer to our Guided Path on Coding Ninjas Studio to upskill yourself in Data Structures and AlgorithmsCompetitive ProgrammingJavaScriptSystem DesignMachine learning and many more! If you want to test your competency in coding, you may check out the mock test series and participate in the contests hosted on Coding Ninjas Studio! But if you have just started your learning process and are looking for questions asked by tech giants like Amazon, Microsoft, Uber, etc; you must look at the problemsinterview experiences, and interview bundle for placement preparations.

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!!

Live masterclass