Problem

Submissions

Hints & solutions

Discuss

Shortest path in an unweighted graph

Moderate

0/80

Average time to solve is 25m

133 upvotes

Asked in companies

Problem statement

The city of Ninjaland is analogous to the unweighted graph. The city has ‘N’ houses numbered from 1 to ‘N’ respectively and are connected by M bidirectional roads. If a road is connecting two houses ‘X’ and ‘Y’ which means you can go from ‘X’ to ‘Y’ or ‘Y’ to ‘X’. It is guaranteed that you can reach any house from any other house via some combination of roads. Two houses are directly connected by at max one road.

A path between house ‘S’ to house ‘T’ is defined as a sequence of vertices from ‘S’ to ‘T’. Where starting house is ‘S’ and the ending house is ‘T’ and there is a road connecting two consecutive houses. Basically, the path looks like this: (S , h1 , h2 , h3 , ... T). you have to find the shortest path from ‘S’ to ‘T’.

For example

In the below map of Ninjaland let say you want to go from S=1 to T=8, the shortest path is (1, 3, 8). You can also go from S=1 to T=8  via (1, 2, 5, 8)  or (1, 4, 6, 7, 8) but these paths are not shortest.

Detailed explanation ( Input/output format, Notes, Images )

Input Format :

The first line of input will have a single positive integer ‘T’, denoting the number of test cases. 

The first line of each test case has two positive integers ‘N’ and ‘M’ denoting the number of houses and the number of roads in the ninja land.

The second line contains two integers ‘S’ and ‘T’ denoting the starting and ending house in the path.

Next M lines each contain two integers ‘X’ and ‘Y’. Which denotes a road between house ‘X’ and house ‘Y’.

Output Format :

You have to return a vector of nodes denoting the shortest path starting from ‘S’ and ending in ‘T’.

If there is more than one shortest path you can return any one of them.

The output of each test case will be "Correct" if you have returned the correct answer, else it will be "Incorrect".

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 <= 100
2 <= N <= 10 ^ 3
1 <= M <= min( N *(N - 1) / 2 , 1000 )
1 <= S, T <= N

Time Limit: 1 sec

Sample input 1 :

Sample Output 1 :

( 1 , 3 , 4 )

Explanation of Sample input 1 :

In the above graph there are two ways to go from 1 to 4 ,
( 1 , 2 , 3 , 4 ) and ( 1 , 3 , 4 ) but the second path is the shortest path.

Sample input 2 :

Sample output 2 :

( 1 , 3 , 8 )

Hint 1

Can you use the fact: the graph has unweighted edges?

Approaches (1)

Approach 1

BFS

Store all the edges in the form of an adjacency list ADJ. if ADJ[X][j] = Y which means there is an edge from X to Y.
Declare a queue Q and push S in it and also declare two vectors VISITED and DISTANCE which will store whether a house is visited or not and what is a distance of the house from house S respectively.
We will also store the PARENT, that store the node from which we will reach the current node. It will help us in building the path afterwards.
Mark S as visited and set DISTANCE[S] = 0
Do the following operations until the Q is not empty.
- Select a vertex which is at the front end of the queue let's say it X. remove it from the queue.
- Iterate to all the neighbouring vertices of X using ADJ. let’s say it Y and if Y is unvisited.
  - push Y in the Q.
  - Mark Y as visited.
  - Set DISTANCE[Y] = DISTANCE[X]+1
  - Make the PARENT[Y] = X
Once we do this we will get the minimum distance of all vertices from S and now we only need to rebuild the path. For this, we can take a vector PATH and push T in it and mark CUR=T.
Do the following until CUR not equal to S
- CUR = PARENT[CUR]
- Add CUR into the PATH
- By this, we will trace the path in the reverse direction.
By doing this we have recreated the path now just reverse the PATH and return it.
Let us take an example of the following graph.
n=4 , m=4
- 1 2
- 1 3
- 2 3
- 3 4
Here we have S = 1 and T = 4, so we start our bfs with node 1
In the first iteration, we have node 1, we will add its neighbours that is 2 and 3 in the queue and set distance of 2 and 3 equal to 2;
Now in the second iteration, we have 2 and there are no unvisited neighbours of 2 so we will move on.
In third iteration we have and there is only one neighbour that is unvisited that is 4 so we will set the distance of 4 equal to 3
we backtrack and we get a path ( 1, 2, 3 )

Time Complexity

O( N + M ), where N is the number of nodes and M is the number of edges.

The Time Complexity required for the BFS traversal of a graph with N nodes and M edges is O( N + M ). Hence, the overall Time Complexity is O(N + M).

Space Complexity

O( N + M ), where N is the number of nodes and M is the number of edges.

Adjacency List required to maintain the graph requires O(N+M) space. Hence, the overall Space Complexity is O( N + M ).

(100% EXP penalty)

Shortest path in an unweighted graph

Shalini Saini

Interview problems

C++ || BFS

#include<unordered_map>

#include<list>

#include<queue>

vector<int> shortestPath( vector<pair<int,int>> edges , int n , int m, int s , int t){

// Write your code here

//creating adj

unordered_map<int,list<int>>adj;

for(int i=0;i<edges.size();i++){

int u=edges[i].first;

int v=edges[i].second;

adj[u].push_back(v);

adj[v].push_back(u);

}

unordered_map<int,bool>visited;

unordered_map<int,int>parent;

queue<int>q;

q.push(s);

visited[s]=true;

parent[s]=-1;

//do BFS

while(!q.empty()){

int front=q.front();

q.pop();

//neighbour nodes and set parents of all

for(auto neighbour:adj[front]){

if(!visited[neighbour]){

q.push(neighbour);

visited[neighbour]=true;

parent[neighbour]=front;

}

//travese the shortest path from parent

vector<int>ans;

int curr=t;

while(curr!=s){

ans.push_back(curr);

curr=parent[curr];

}

ans.push_back(s);

reverse(ans.begin(),ans.end());

return ans;

}

13 views

0 replies

0 upvotes

Surajit Roy

Interview problems

Shortest path in an unweighted graph

#include<unordered_map>

#include<queue>

#include<list>

vector<int> shortestPath( vector<pair<int,int>> edges , int n , int m, int s , int t){

//create adj list

unordered_map<int, list<int> > adj;

for(int i=0; i<edges.size(); i++){

int u = edges[i].first;

int v = edges[i].second;

adj[u].push_back(v);

adj[v].push_back(u);

}

//do bfs

unordered_map<int, bool> visited;

unordered_map<int,int> parent;

queue<int> q;

q.push(s);

parent[s] = -1;

visited[s] = true;

while(!q.empty()){

int front = q.front();

q.pop();

for(auto i: adj[front]) {

if(!visited[i]) {

visited[i] = true;

parent[i] = front;

q.push(i);

}

//prepare shortest path

vector<int> ans;

int currentNode = t;

ans.push_back(t);

while(currentNode != s) {

currentNode = parent[currentNode];

ans.push_back(currentNode);

}

reverse(ans.begin(), ans.end());

return ans;

}

53 views

0 replies

0 upvotes

Aman Raj

Interview problems

Using simple queue DS and implementing Dijkstra

vector<int> shortestPath( vector<pair<int,int>> edges , int n , int m, int s , int t){

//creating adjacency list

vector<int> adj[n+1];

for(auto it: edges){

adj[it.first].push_back(it.second);

adj[it.second].push_back(it.first);

}

vector<int> parent(n+1), pathlen(n+1, 1e9);

pathlen[s] = 0;

parent[s] = s;

queue<pair<int, int>> q;

q.push({0, s});

while(!q.empty()){

int dist = q.front().first;

int node = q.front().second;

q.pop();

//if(node == t) break;

for(auto it: adj[node]){

if(pathlen[it]>dist+1){

pathlen[it] = dist+1;

parent[it] = node;

q.push({dist+1, it});

}

int node = t;

vector<int> ans;

while(parent[node] != node){

ans.push_back(node);

node = parent[node];

}

ans.push_back(s);

reverse(ans.begin(), ans.end());

return ans;

}

17 views

0 replies

0 upvotes

Aman Raj

Interview problems

Using simple Dijkstra

vector<int> shortestPath( vector<pair<int,int>> edges , int n , int m, int s , int t){
    //creating adjacency list
    vector<int> adj[n+1];
    for(auto it: edges){
        adj[it.first].push_back(it.second);
        adj[it.second].push_back(it.first);
    }

    vector<int> parent(n+1), pathlen(n+1, 1e9);
    pathlen[s] = 0;
    parent[s] = s;

    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push({0, s});
    while(!pq.empty()){
        int dist = pq.top().first;
        int node = pq.top().second;
        pq.pop();
        
        if(node == t) break;
        
        for(auto it: adj[node]){
            if(pathlen[it]>dist+1){
                pathlen[it] = dist+1;
                parent[it] = node;
                pq.push({dist+1, it});
            }
        }
    }

    int node = t;
    vector<int> ans;
    while(parent[node] != node){
        ans.push_back(node);
        node = parent[node];
    }
    ans.push_back(s);
    reverse(ans.begin(), ans.end());
    return ans;
}

15 views

0 replies

0 upvotes

Nishant Kumar Singh

Interview problems

love babbar

#include<unordered_map>

#include<list>

#include<queue>

vector<int> shortestPath( vector<pair<int,int>> edges , int n , int m, int s , int t){

unordered_map<int,list<int> >adj;

for(int i=0;i<edges.size();i++){

int u = edges[i].first;

int v = edges[i].second;

adj[u].push_back(v);

adj[v].push_back(u);

}

unordered_map<int,bool>visited;

unordered_map<int,int>parent;

queue<int>q;

q.push(s);

parent[s] = -1;

visited[s] = true;

//do bfs

while(!q.empty()){

int front = q.front();

q.pop();

for(auto i:adj[front]){

if(!visited[i]){

visited[i]=true;

parent[i]=front;

q.push(i);

}

//prepare shortest path

vector<int>ans;

int currentNode = t;

ans.push_back(t);

while(currentNode != s){

currentNode = parent[currentNode];

ans.push_back(currentNode);

}

reverse(ans.begin(),ans.end());

return ans;

}

19 views

0 replies

0 upvotes

Yash Tawde

Interview problems

cpp soln using bfs

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

void findPath(int s, int t, vector<int>&ans, unordered_map<int,int>&parent)
{
    if(t == s)
    {
        ans.push_back(t);
        return;
    }
    findPath(s, parent[t], ans, parent);
    ans.push_back(t);
}

vector<int> shortestPath( vector<pair<int,int>> edges , int n , int m, int s , int t){
	// create an adjacency list.    
    unordered_map<int,list<int>>adjList;
    for(auto edge : edges)
    {
        int u = edge.first;
        int v = edge.second;
        adjList[u].push_back(v);
        adjList[v].push_back(u);
    }

    // created the parent and visited arr.
    unordered_map<int,bool>vis;
    unordered_map<int,int>parent;

    // created a queue.
    queue<int>q;
    q.push(s);
    vis[s] = true;
    parent[s] = -1;

    // prepare the parent array for us.
    while(!q.empty())
    {
        int f = q.front();
        q.pop();
        for(auto x : adjList[f])
        {
            if(!vis[x])
            {
                q.push(x);
                vis[x] = true;
                parent[x] = f;
            }
        }
    }

    vector<int>ans;

    // backtrack the parents from the dest to src.
    findPath(s, t, ans, parent);
    return ans;
}

128 views

0 replies

0 upvotes

Deependra Parmar

Interview problems

Best C++ Solution using BFS 🔥🚀✅

#include <bits/stdc++.h>


vector<int> shortestPath( vector<pair<int,int>> edges , int n , int m, int s , int t){
    
    vector<vector<int>> adj(n+1);


    for(int i=0; i<edges.size(); i++){
        int u = edges[i].first;
        int v = edges[i].second;


        adj[u].push_back(v);
        adj[v].push_back(u);
    }   


    // do bfs
    unordered_map<int, bool> visited(n+1);
    unordered_map<int, int> parent(n+1);


    queue<int> q;
    q.push(s);
    parent[s] = -1;
    visited[s] = true;


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


        for(auto i: adj[front]){
            if(!visited[i]){
                visited[i] = true;
                parent[i] = front;
                q.push(i);
            }
        }
    }


    // finding the shortest path
    vector<int> ans;
    int currentNode = t;
    ans.push_back(t);


    while(currentNode != s){
        currentNode = parent[currentNode];
        ans.push_back(currentNode);
    }


    reverse(ans.begin(), ans.end());


    return ans;
}

106 views

2 replies

0 upvotes

Abhishek Sachdeva

Interview problems

shortest path || c++ code || upvote

void solve(vector<vector<int>>&adj,vector<bool>&visited,int pointer,vector<int>&parent)

{

visited[pointer]=true;

parent[pointer]=-1;

queue<int>q;

q.push(pointer);

while(!q.empty())

{

int front = q.front();

q.pop();

for(auto child:adj[front])

{

if(!visited[child])

{

visited[child]=true;

parent[child] = front;

q.push(child);

}

vector<int> shortestPath( vector<pair<int,int>> edges , int n , int m, int s , int t){

// Write your code here

vector<vector<int>>adj(n+1);

for(int i=0; i<edges.size(); ++i)

{

int x = edges[i].first;

int y = edges[i].second;

adj[x].push_back(y);

adj[y].push_back(x);

}

vector<bool>visited(n+1,false);

vector<int>parent(n+1,-1);

solve(adj,visited,s,parent);

vector<int>ans;

int currentnode = t;

while(currentnode!=-1)

{

ans.push_back(currentnode);

currentnode = parent[currentnode];

}

reverse(ans.begin(),ans.end());

return ans;

}

135 views

0 replies

1 upvote

Abdul Ikram

Interview problems

Easy C++ Solution (BFS) || All Test Case Passed

#include<unordered_map>

#include<list>

vector<int> shortestPath( vector<pair<int,int>> edges , int n , int m, int s , int t){

unordered_map<int, list<int>> adj;

for(int i=0;i<edges.size();i=i+1){

adj[edges[i].first].push_back(edges[i].second);

adj[edges[i].second].push_back(edges[i].first);

}

unordered_map<int, bool> visited;

unordered_map<int, int> parent;

queue<int> que;

que.push(s);

visited[s] = true;

parent[s] = -1;

while(!que.empty()){

for(auto neighbour:adj[que.front()]){

if(!visited[neighbour]){

que.push(neighbour);

visited[neighbour] = true;

parent[neighbour] = que.front();

}

que.pop();

}

vector<int> path;

int currNode = t;

path.push_back(currNode);

while(currNode!=s){

currNode = parent[currNode];

path.push_back(currNode);

}

reverse(path.begin(), path.end());

return path;

}

99 views

0 replies

1 upvote

Sheil Bhan

Interview problems

BFS traversal C++ easy soln

#include <unordered_map>

#include <queue>

#include <list>

vector<int> shortestPath( vector<pair<int,int>> edges , int n , int m, int s , int t){

unordered_map<int,list<int> > adj;

for(int i = 0; i<edges.size(); i++){

int u = edges[i].first;

int v = edges[i].second;

adj[u].push_back(v);

adj[v].push_back(u);

}

unordered_map<int,bool > visited;

unordered_map<int,int> parent;

queue<int> q;

q.push(s);

parent[s] = -1;

visited[s] = true;

while(!q.empty()){

int front = q.front();

q.pop();

for(auto i: adj[front]){

if(!visited[i]){

visited[i] = true;

parent[i] = front;

q.push(i);

}

vector<int> ans;

int currentNode = t;

ans.push_back(t);

while(currentNode != s){

currentNode = parent[currentNode];

ans.push_back(currentNode);

}

reverse(ans.begin(),ans.end());

return ans;

}

84 views

0 replies

0 upvotes

Console