# Shortest path in an unweighted graph

## 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). 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 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,

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.

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

## 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,

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.

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

Graph(int num_vertices, int num_edges){

this->V = num_vertices;

this->E = num_edges;

}

}

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

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

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

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

// A directed graph using
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;

// Constructor
public Main(int vertices)
{

// initialise vertex count
this.v = vertices;

}

// utility method to initialise
@SuppressWarnings("unchecked")
{

for (int i = 0; i < v; i++) {
}
}

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

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

// 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
for (Integer i : adjList[u]) {
if (!isVisited[i]) {
// store current node
// in path[]
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);

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

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:

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.

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++ 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
Graph(int num_vertices, int num_edges){
this->V = num_vertices;
this->E = num_edges;
}
}
// 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
// make necessary updations
}
}
}
}
}
// 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
// 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

``````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<>();
}

}

//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
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){
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)

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

Output:

``[A, B, E]``

### I Implementation in 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
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)

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.

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

### When can BFS be applied to obtain the Shortest path in O(|V|+|E|) time?

Note that BFS cannot always find the Shortest path in O(|V|+|E|) time. There are cases where it can be applied, i.e., if the edges have no weights or equal weights. You might find its application in problems having 2 or 3 different edge weights.

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