Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
What do we mean by the Shortest Path in an unweighted graph?
3.
Approach 1: Naive
3.1.
PseudoCode
3.2.
Implementation in C++
3.3.
C++
3.3.1.
Output:
3.4.
Implementation in Java
3.5.
Java
3.5.1.
Output:
3.6.
Complexity Analysis
4.
Approach 2: Efficient
4.1.
Implementation in C++
4.2.
C++
4.2.1.
Output:
4.3.
Implementation in Java
4.4.
Java
4.4.1.
Output:
4.5.
Implementation in Python
4.6.
Python
4.6.1.
   Output:
4.7.
Complexity Analysis
5.
Frequently Asked Questions
5.1.
Can we use the Dijkstra Algorithm to compute the shortest path?
5.2.
Can there be multiple shortest paths in a Graph?
5.3.
How do you find the shortest path in an undirected graph?
5.4.
What is the shortest path in undirected graph BFS?
6.
Conclusion
6.1.
Recommended Readings
Last Updated: Mar 27, 2024
Hard

Shortest Path in an Unweighted Graph

Author aniket verma
4 upvotes
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

Introduction

In this blog, we will discuss how to find the Shortest path in an unweighted graph. It is a very important problem to get a strong grip over graph-based algorithms and their applications and has also been asked in many interviews as well as in various competitive coding contests (see Graph Algorithms for Competitive Programming).

shortest path in undirected graph

A common prerequisite before any graph problem is the knowledge of graphs and related terminologies, recursion, Data Structures such as stacks, queues, trees, and the 2 standard algorithms DFS Algorithm and BFS. Without knowing this, it is not recommended to jump on to graphs. Nevertheless, we’ll try to cover each point that is required to find the shortest path in an unweighted graph.

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

Well, it’s a trivial question, but still, for the sake of clarity, we’ll define that:

Let G = (V, E) be an undirected graph with E edges and vertices. Let T be the shortest path between any 2 vertices in the graph such that there is no other path in the graph between any 2 vertices whose sum of edge weights is less than T’s sum of edge weights. 

In the case of unweighted graphs, there will be no edge weights. In that case, the shortest path T will become the path between the given 2 vertices with the minimum number of edges.


NOTE: Shortest path between 2 vertices is defined only when the vertices are in the same graph, i.e., the graph should not be disconnected.

We’ll be talking about Undirected Graphs in this Blog.

Let’s look at an example first.

Given an Unweighted Graph G,

Unweighted Graph

Input:  Starting Node Src = 1 and Ending Node Dest = 8.

Output:  list of nodes denoting the shortest path from Src to Dest, i.e., 1->3->8.


Note how we got the shortest path. We see that the path is of length 2, and there is no other path with a length less than 2.

Also read - Shortest Path in a Directed Acyclic Graph

Recommended: Try the Problem yourself before moving on to the solution

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 1: Naive

What is the first approach that comes to our mind? Don’t think about any optimizations for now. The most basic approach that immediately comes to mind is finding all possible paths from source to destination and then comparing them with each other to find the shortest path.

So let’s dry run over the above approach for the given unweighted graph G,

Unweighted Graph

So all paths Ti’s from src = 1 to dest = 8 are 

T1 = 1 -> 2 -> 5 -> 8

T2 = 1-> 3 -> 8

T3 = 1-> 4 - > 6 -> 7 -> 8

From all the paths listed above, we see that T2 is the shortest path, with a length of 2.

If you look at the paths computed, see how we traverse the graph first, we traverse node 2 and find all paths from node 8. We traverse through all paths from node 3 to node 8 and then from node 4 to node 8. Do you observe any repetition that is taking place here?

When we start traversing the adjacent nodes connected to node 1, we observe that the problem becomes finding the path from the adjacent node to node 8. Hence recursively find the path from node 1 to node 8. If we reach, we can add the path to our possible Shortest path list; if no further paths are possible from that node, we can backtrack and visit all the other paths from the remaining adjacent nodes.

Hence now we can formulate our approach as the brute-force approach:

  1. Traverse all adjacent nodes and recursively find the paths from src node to dest node.
  2. Find the path with the shortest size and return that path.

Also read - BFS in Disconnected Graph

IMPORTANT NOTE: This Algorithm works only for a graph with no cycles.

PseudoCode

# Let's assume that the function computeAllPaths(Src, Dest) returns all paths from Src to Dest.

Algorithm

procedure ShortestPath(Graph G, Src, Dest):

 

1.    List_of_paths ← computeAllPaths(G, Src, Dest)

2.    Shortest_path ← empty list

3.    for path in list_of_paths do  

4.     if Shortest_path is empty do

5.              Shortest_path ← path

6.     end if 

7.       else if Shortest_path.size() > path.size() do

8.       Shortest_path ← path

9.       end else if

10.   return Shortest_path

11.   end procedure

 

Implementation in C++

  • C++

C++

//C++ program to find the Shortest Path in an Unweighted Graph
#include <bits/stdc++.h>
using namespace std;
// Graph class implemented using an adjacency list

class Graph{

public:
   int V;  // Number of Vertices
   int E;  // Number of Edges
   vector<int> *adj; // adjacency list
   Graph(int num_vertices, int num_edges){
       this->V = num_vertices;
       this->E = num_edges;
       this->adj = new vector<int>[num_vertices];
   }
   // function to add Edge
void addEdge(int u, int v){
       adj[u-1].push_back(v-1);
       adj[v-1].push_back(u-1);
}

   // function to compute all paths
void computeAllPaths(int src, int dest, vector<int> &path, vector<bool> &vis, vector<vector<int>> &paths){
       if(vis[src]){ // if this node is already visited then return
           return ;
       }
       // if src == dest means that we have reached the destination and found the path
       if(src == dest){
           path.push_back(src);
           paths.push_back(path);
           path.pop_back();
           return;
       }
       // mark current node as visited
       vis[src] = 1;
       path.push_back(src);
       // traverse the path via current node's adjacent nodes
       for(int node: this->adj[src]){
           if(!vis[node]){  // if adjacent node is not visited
               // path.push_back(node);  // push to the possible path list
               computeAllPaths(node, dest, path, vis, paths); // recursively traverse path
               // path.pop_back(); // pop_back from the possible path list
           }
       }
       vis[src] = 0; // mark current node as unvisited
       path.pop_back(); // pop the current source node
   }

   // function that prints out the shortest path   
void ShortestPath(int src, int dest){
      vector<int> path; // possible path list
      vector<bool> vis(V, 0); // visited list
      vector<vector<int>> paths; // list of all paths from src to dest
      computeAllPaths(src, dest, path, vis, paths); // find All paths
      vector<int> Shortest_path; // vector to store the Shortest_path
      for(vector<int> v: paths){
          // find the Shortest_path
          if(Shortest_path.size()==0 or (Shortest_path.size()>v.size())){
              Shortest_path = v;
          }
      }
      cout<<"The Shortest Path of the Unweighted Graph is: ";
      // print the shortest path
      for(int i=0;i<Shortest_path.size();++i){
          if(i!=Shortest_path.size()-1){
              cout<<Shortest_path[i]+1<<" -> ";
          }else{
              cout<<Shortest_path[i]+1<<'\n';
          }
      }
      cout<<"The length is "<<Shortest_path.size();
   }
};

int main() {
   // Number of Edges and Vertices
int num_vertices = 8;
int num_edges = 9;
Graph G(num_vertices, num_edges); // Graph G
   // add all edges to graph
G.addEdge(1, 2);
G.addEdge(2, 1);
G.addEdge(1, 3);
G.addEdge(3, 1);
G.addEdge(1, 4);
G.addEdge(4, 1);
G.addEdge(3, 8);
G.addEdge(8, 3);
G.addEdge(5, 2);
G.addEdge(2, 5);
G.addEdge(4, 6);
G.addEdge(6, 4);
G.addEdge(7, 6);
G.addEdge(6, 7);
G.addEdge(5, 8);
G.addEdge(8, 5);
G.addEdge(8, 7);
G.addEdge(7, 8);
// compute the Shortest_path
int src = 1; int dest = 8;
G.ShortestPath(src-1, dest-1); // 0-based indexing
return 0;
}

Output:

The Shortest Path of the Unweighted Graph is: 1 -> 3 -> 8

Implementation in Java

  • Java

Java

import java.util.ArrayList;
import java.util.List;

// A directed graph using
// adjacency list representation
public class Main {

// No. of vertices in graph
static String ans="";
static int mini=Integer.MAX_VALUE;
public static List<Integer> shortestPath;
private int v;

// adjacency list
private ArrayList<Integer>[] adjList;

// Constructor
public Main(int vertices)
{

// initialise vertex count
this.v = vertices;

// initialise adjacency list
initAdjList();
}

// utility method to initialise
// adjacency list
@SuppressWarnings("unchecked")
private void initAdjList()
{
adjList = new ArrayList[v];

for (int i = 0; i < v; i++) {
adjList[i] = new ArrayList<>();
}
}

// add edge from u to v
public void addEdge(int u, int v)
{
// Add v to u's list.
adjList[u].add(v);
}

// Prints all paths from
// 's' to 'd'
public void printAllPaths(int s, int d)
{
boolean[] isVisited = new boolean[v];
ArrayList<Integer> pathList = new ArrayList<>();

// add source to path[]
pathList.add(s);

// Call recursive utility
printAllPathsUtil(s, d, isVisited, pathList);
}

// A recursive function to print
// all paths from 'u' to 'd'.
// isVisited[] keeps track of
// vertices in current path.
// localPathList<> stores actual
// vertices in the current path
private void printAllPathsUtil(Integer u, Integer d,
boolean[] isVisited,
List<Integer> localPathList)
{

if (u.equals(d)) {
if(localPathList.size()<mini)
{
mini=localPathList.size();

ans = localPathList.toString();

}

// if match found then no need to traverse more till depth
return;
}

// Mark the current node
isVisited[u] = true;

// Recur for all the vertices
// adjacent to current vertex
for (Integer i : adjList[u]) {
if (!isVisited[i]) {
// store current node
// in path[]
localPathList.add(i);
printAllPathsUtil(i, d, isVisited, localPathList);

// remove current node
// in path[]
localPathList.remove(i);
}
}

// Mark the current node
isVisited[u] = false;
}

// Driver program
public static void main(String[] args)
{
// Create a sample graph
Main g = new Main(4);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(0, 3);
g.addEdge(2, 0);
g.addEdge(2, 1);
g.addEdge(1, 3);

// arbitrary source
int s = 2;

// arbitrary destination
int d = 3;

System.out.println(
"Shortest Path from "
+ s + " to " + d);
g.printAllPaths(s, d);


System.out.println(ans);
}
}

 

Output:

Shortest Path from 2 to 3 [2, 0, 3]

Complexity Analysis

Time Complexity: O(|V|!)

We start from the source node, and then we have |V|-1 nodes to choose from, further we can have at most |V|-2, and, so on.   

Hence the time complexity is O(|V| x |V| -1 x |V|-2 x ….)  = O(|V|!).

Space complexity: O(|V|) at the worst case.

It is O(|V|) because we are using an extra visited array. 

The above algorithm has some loopholes that we need to find the Shortest path in an unweighted graph efficiently.


So let’s think about an efficient approach to solve the problem.

Approach 2: Efficient

If we want to build up an efficient solution, we will need to find out if there is any redundancy or any repetition that we are doing.

So the redundancy in our above approach is that we are finding all possible paths and then finding the shortest path out of the computed paths.

So we aim to avoid computing all paths. Instead, we should be finding the shortest path progressively. 


The most important fact we should know is that BFS traversal can be used to find the shortest path in an unweighted graph in O(|V| + |E|) time.

Let’s visualize and build an intuition about why BFS will compute the shortest path in an unweighted graph from a given source node to the destination node.

Say we have the following unweighted graph G.

Unweighted Graph

We have taken a complex graph to be generalized further to all graphs of the same nature. We want to find the shortest path in the unweighted graph G from the source node 1 to the destination node N. When we start traversing the graph using a BFS, each node will be traversed one by one. Finally, the traversed nodes will result in a tree which is usually termed the spanning tree. So let’s call it the BFS spanning tree.

Let’s create the Spanning tree of the complex graph in the order BFS traverses it. (We will traverse from node 1, and we will traverse the adjacent nodes in ascending order. You can traverse in any order you feel like. The connection of edges in the resultant spanning tree could change.)

Resultant spanning tree:

Spanning Tree

This is what the spanning tree will look like for the complex graph spanned by BFS traversal.

Now see, when we apply BFS traversal from a given source node, we start traversing along with its breadth, i.e., all the adjacent nodes will be traversed before the deeper nodes relative to the source node are traversed.


Just for the sake of visualization, we will just rotate the above spanning tree. 

Spanning Tree

Now observe when we start traversing; all nodes at a particular distance from the source node will get traversed first. And this is the closest distance from the source node. Because, if it all has some smaller path, it would have been visited till then, as we are traversing all nodes along with a node’s breadth and not the depth.  

Now there must be 2 questions that might arise. The first is why I couldn’t traverse it using DFS? Secondly, how to compute the path from source to destination?

The answer to the first question is on using DFS over BFS; DFS traverses along with the depth and not the breadth. It will go as deep as the branch, and if at all you reach the destination first, you cannot guarantee that it is the shortest path from the source node.

The second question answer is that while traversing a node, we can maintain its distance from the source node in a list and store its parent node in a parent list.

When we complete our BFS traversal, we then traverse back from the destination node to the source node using the parent list. Note that since it’s an undirected graph, we can traverse either way, i.e., from the destination node to the source node or vice-versa, the path will still be the shortest.

 

Hence we have improved from a brute-force approach to an efficient approach.

Now let’s formulate our approach :

  1. Traverse the graph from the source node using a BFS traversal.
  2. Update the distance of the nodes from the source node during the traversal in a distance list and maintain a parent list to update the parent of the visited node.
  3. When we reach the destination, we can print the shortest path from the source to the destination by backtracking along with the parent list from the destination node to the source node.

Implementation in C++

  • C++

C++

//C++ program to find the Shortest Path in an Unweighted Graph
#include <bits/stdc++.h>
using namespace std;
// Graph class implemented using an adjacency list
class Graph{
public:
   int V;  // Number of Vertices
   int E;  // Number of Edges
   vector<int> *adj; // adjacency list
   Graph(int num_vertices, int num_edges){
       this->V = num_vertices;
       this->E = num_edges;
       this->adj = new vector<int>[num_vertices];
   }
   // function to add Edge
   void addEdge(int u, int v){
       adj[u-1].push_back(v-1);
       adj[v-1].push_back(u-1);
   }
   // BFS traversal that updates the dist and parent vector
   void BFS(int src, int dest, vector<int> &dist, vector<int> &parent){
       vector<bool> vis(V, 0);  // vis vector to mark if node is visited
       queue<int> q; // queue to store nodes to be visited along the breadth
       q.push(src); // push src node to queue
       vis[src] = 1;// mark source node as visitedi
       while(!q.empty()){
           int q_size = q.size();  // traverse all nodes along the breadth
           while(q_size--){
               int node = q.front(); // extract the front node
               q.pop(); // pop the node
               vis[node] = 1; // mark it visited
               // traverse along the node's breadth
               for(int adjNode : this->adj[node]){
                   if(!vis[adjNode]){  // if adjNode is not visited
                       // make necessary updations
                       vis[adjNode] = 1;
                       dist[adjNode] = dist[node] + 1;
                       parent[adjNode] = node;
                       q.push(adjNode);
                   }
               }
           }
       }
   }
   // function that computes the shortest path and prints it
   void findShortestPath(int src, int dest){
       vector<int> dist(V, 0); // dist vector
       vector<int> parent(V); // parent vector
       for(int i=0;i<V;++i){
          parent[i] = i;  // initialising the parent to node itself
       }
       // BFS that updates the parent and dist vector
       // and helps in computing the shortest path
       BFS(src, dest, dist, parent);
       //stack to store the path from destination to source
       // while backtracking using the parent vector
       stack<int> st;
       // backtracking loop
       while(parent[dest]!=dest){
           st.push(dest);
           dest = parent[dest];
       }
       st.push(dest);  // when the loop ends, it means we reach the source node  
       int Path_length = st.size(); //shortest path length
       // print the shortest path along with its length
       cout<<"The Shortest Path of the Unweighted Graph is: "; 
       while(st.size()>1){
           cout<<st.top()+1<<" -> ";
           st.pop();
       }
       cout<<st.top()+1<<"\n";
       cout<<"The length is "<<Path_length;
   }

};

int main() {

   // Number of Edges and Vertices

int num_vertices = 8;

int num_edges = 9;
Graph G(num_vertices, num_edges); // Graph G   
   // add all edges to graph
G.addEdge(1, 2);
G.addEdge(2, 1);
G.addEdge(1, 3);
G.addEdge(3, 1);
G.addEdge(1, 4);
G.addEdge(4, 1);
G.addEdge(3, 8);
G.addEdge(8, 3);
G.addEdge(5, 2);
G.addEdge(2, 5);
G.addEdge(4, 6);
G.addEdge(6, 4);
G.addEdge(7, 6);
G.addEdge(6, 7);
G.addEdge(5, 8);
G.addEdge(8, 5);
G.addEdge(8, 7);
G.addEdge(7, 8);
// compute the Shortest_path
int src = 1; int dest = 8;
G.findShortestPath(src-1, dest-1);
return 0;
}

 

Output:

The Shortest Path of the Unweighted Graph is: 1 -> 3 -> 8
The length is 3

Implementation in Java

  • Java

Java

import java.util.*;

// Graph class implemented using an adjacency list
class Node{
String name;
List<Node> neighbors;
boolean visited = false;
Node prev = null;

Node(String name){
this.name = name;
this.neighbors = new ArrayList<>();
}

// function to add Edge
void add_neighbor(Node node){
this.neighbors.add(node);
node.neighbors.add(this);
}

//Node representation
public String toString(){
return this.name;
}
}

//class implmenting the algorithm
class ShortestPath{
Node start, end;

ShortestPath(Node start, Node end){
this.start = start;
this.end = end;
}
// BFS traversal that updates the dist and parent vector

public void bfs(){
Queue<Node> queue = new LinkedList<>();// queue to store nodes to be visited along the breadth

start.visited = true; // mark source node as visitedi
queue.add(start); // push src node to queue

while(!queue.isEmpty()){
Node current_node = queue.poll();// traverse all nodes along the breadth
// traverse along the node's breadth
for(Node node: current_node.neighbors){
if(!node.visited){
node.visited =true;// // mark it visited
queue.add(node);
node.prev = current_node;
if(node==end){
queue.clear();
break;
}
}
}
}
trace_route();
}

// function that computes the shortest path and prints it
private void trace_route(){
Node node = end;
List<Node> route = new ArrayList<>();
//Loop until node is null to reach start node
//becasue start.prev == null
while(node != null){
route.add(node);
node = node.prev;
}
//Reverse the route - bring start to the front
Collections.reverse(route);
//Output the route
System.out.println(route);
}
}

//Driver Code
class Main {
public static void main(String[] args) {
//create nodes
Node node_A = new Node("A");
Node node_B = new Node("B");
Node node_C = new Node("C");
Node node_D = new Node("D");
Node node_E = new Node("E");

//connect nodes (i.e. create graph)
node_A.add_neighbor(node_B);
node_B.add_neighbor(node_C);
node_C.add_neighbor(node_D);
node_D.add_neighbor(node_E);
node_B.add_neighbor(node_E);

new ShortestPath(node_A, node_E).bfs();
}
}


Output:

[A, B, E]

Implementation in Python

  • Python

Python

#class representing node of a graph
class Node:
def __init__(self, name):
self.name = name
self.prev = None
self.neighbors = []
self.visited = False

#Method to connect nodes
def add_neighbor(self, node):
self.neighbors.append(node)
node.neighbors.append(self)

#Node representaion
def __repr__(self):
return self.name

class ShortestPath:
def __init__(self, start, end):
self.start = start
self.end = end

def bfs(self):
#Create queue
queue = []
#Visit and add the start node to the queue
self.start.visited = True
queue.append(self.start)

#BFS until queue is empty
while queue:
#Pop a node from queue for search operation
current_node = queue.pop(0)
#Loop through neighbors nodes to find the 'end' node
for node in current_node.neighbors:
if not node.visited:
#visit and add neighbors nodes to the queue
node.visited = True
queue.append(node)
#update its preceding node
node.prev = current_node
#stop BFS if the visited node is the end node
if node == self.end:
queue.clear()
break;
#BFS completed, now trace the route
self.trace_route()

#Function to trace the route using preceding nodes
def trace_route(self):
node = self.end
route = []
#start node has no preceding node
#so loop until node->prev is null
while node:
route.append(node)
node = node.prev
#reverse the route bring start to the front
route.reverse()
#output route
print(route)

if __name__ == '__main__':
#create nodes
node_A = Node('A')
node_B = Node('B')
node_C = Node('C')
node_D = Node('D')
node_E = Node('E')
#connect nodes (i.e. create graph)
node_A.add_neighbor(node_B)
node_B.add_neighbor(node_C)
node_C.add_neighbor(node_D)
node_D.add_neighbor(node_E)
node_B.add_neighbor(node_E)

ShortestPath(node_A, node_E).bfs()

   
Output:

[A, B, E]

Complexity Analysis

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

We traversed the graph using a BFS traversal that takes O(|V|  + |E|) time.

Space Complexity: O(|V|) in the worst case, as the maximum nodes that can be stored will be O(|V|).

Hence we reached an efficient solution. 

 

Note: The problem could also be solved using Bellman-Ford or Dijkstra; both are single-source shortest path algorithms and are generally used in the case of weighted graphs, with Dijkstra only being used in the case of graphs having non-negative weights.

Frequently Asked Questions

Can we use the Dijkstra Algorithm to compute the shortest path?

Yes, we can use Dijkstra Algorithm to compute the shortest path, but there are some constraints that the graph shouldn’t contain a negative weighted cycle.

Can there be multiple shortest paths in a Graph?

Yes, we can find multiple shortest paths in a Graph.

How do you find the shortest path in an undirected graph?

You can find the shortest path in an undirected graph using algorithms like Dijkstra's algorithm or Breadth-First Search (BFS) starting from the source vertex.

What is the shortest path in undirected graph BFS?

In an undirected graph, you can find the shortest path using Breadth-First Search (BFS) starting from the source vertex and stopping when you reach the target vertex.

Conclusion

This article taught us how to find the Shortest path in an unweighted graph by approaching the problem using a recursive approach followed by an efficient solution. We discussed a recursive and an iterative implementation using illustrations, pseudocode, and then proper code.

We hope you could take away critical techniques like analyzing problems by walking over the execution of the examples and finding out the recursive pattern followed in most graph problems. Then, we could reduce the extra computations by observing how traversing a graph along breadth and depth helps us solve graph problems.

Recommended Problems:

Recommended Readings

You can check out The Interview guide for Product Based Companies as well as some of the Popular interview problems from top tech companies like Amazon, Adobe, Google, Uber, Microsoft, etc.

Refer to our guided pathways on Code studio to learn more about DSACompetitive ProgrammingSystem Design, etc. Enroll in our courses, and use the accessible sample exams and questions as a guide.

Previous article
Shortest path in a directed acyclic graph
Next article
Minimum possible modifications in the matrix to reach the destination
Live masterclass