Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
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.
Frequently Asked Questions
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

Author 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.

Multi Source Shortest Path in Unweighted Graph

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

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.
nitialize 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.

 

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.
we run a loop, find the shortest distance between the src variable and multiple sources,
  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();
       
       for(auto it:adj[node]){
           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);      
    }
  }
void addEdge(vector<int> adj[], int u, int v)
{
    adj[u].push_back(v);
    adj[v].push_back(u);
}
// Driver Code
int main()
{ // Number of vertices
    int n = 6;
    vector<int> adj[n + 1];
    // Edges
    addEdge(adj, 1, 2);
    addEdge(adj, 1, 5);
    addEdge(adj, 2, 3);
    addEdge(adj, 3, 4);
    addEdge(adj, 3, 6);
    addEdge(adj, 4, 5);
    addEdge(adj, 4, 6);
    // Sources
    int sources[] = { 3, 5 };
    int S = sizeof(sources) / sizeof(sources[0]);
	cout<<" Multi Source Shortest Path in Unweighted Graph "<<endl;
  	Multi_source_shortest_path(adj, n, sources, S)
    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
void Multisource_BFS(vector<int> adj[],queue<int>q,int n,bool visited[]
, int dist[])
{
    while(!q.empty())
    {
        int k = q.front();
        q.pop();
    
        for(int i = 0;i<adj[k].size();i++)
        {
            if(!visited[adj[k][i]])
            {
    
                // Pushing the adjacent unvisited vertices
                // with distance from current source = this
                // vertex's distance + 1
                q.push(adj[k][i]);
                dist[i] = dist[k] + 1;
                visited[adj[k][i]] = true;
            }
        }
    }
}


// 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;
    vector<int> adj[n + 1];
    // Edges
    addEdge(adj, 1, 2);
    addEdge(adj, 1, 5);
    addEdge(adj, 2, 3);
    addEdge(adj, 3, 4);
    addEdge(adj, 3, 6);
    addEdge(adj, 4, 5);
    addEdge(adj, 4, 6);
    // Sources
    int sources[] = { 3, 5 };
    int S = sizeof(sources) / sizeof(sources[0]);
	cout<<"Multi Source Shortest Path in Unweighted Graph "<<endl;
  	Multi_source_shortest_path(adj, n, sources, S);
    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.

Frequently Asked Questions

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

Thank you

Previous article
Shortest Distance Between Given Nodes in a Bidirectional Weighted Graph by Removing any K Edges
Next article
Print all Hamiltonian Cycles in an Undirected Graph.
Live masterclass