Do you think IIT Guwahati certified course can help you in your career?
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 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 V 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.
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:
Traverse all adjacent nodes and recursively find the paths from src node to dest node.
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
procedureShortestPath(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; }
You can also try this code with Online C++ Compiler
// 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<>();
// 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); } }
You can also try this code with Online Java Compiler
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 :
Traverse the graph from the source node using a BFS traversal.
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.
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; }
You can also try this code with Online C++ Compiler
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");
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)
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.
Refer to our guided pathways on Code studio to learn more about DSA, Competitive Programming, System Design, etc. Enroll in our courses, and use the accessible sample exams and questions as a guide.
85+ registered