Shortest path in an unweighted graph

aniket verma
Last Updated: May 24, 2022
Difficulty Level :
MEDIUM

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

 

Source: link

 

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

    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

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.

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

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]

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

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.

Recommended Reading

You can also check out some Problems, Interview Experiences, and Guided Paths for topics such as Data Structure and Algorithms and several Courses taught by industry experts on CodeStudio

Was this article helpful ?
0 upvotes

Comments

No comments yet

Be the first to share what you think