Shortest Path in Unweighted Undirected Graph using BFS

Algorithm

Problem: Given an unweighted undirected graph, we have to find the shortest path from the given source to the given destination using the Breadth-First Search algorithm.

Shortest path in an unweighted graph

The idea is to traverse the graph using Breadth-First Search Traversal until we reach the end node and print the route by tracing back the path to the start node.

How to check whether recached the end node?

Every time we visit a node, we compare it with the end node. If they match, we stop BFS.

How to stop BFS when we reach the end node?

BFS uses the queue to visit the next node, it runs until the queue is empty.

So, we can either clear the queue to stop BFS or use an explicit boolean flag such as end_reached to mark the end of BFS.

How to trace path from end to start node?

To trace the route, we use an extra node property called prev that stores the reference of the preceding node.

Every time we visit a node, we also update its prev value.

Trace back the shortest route

Using the prev value, we trace the route back from the end node to the starting node. Example for the given graph, route = E <- B <- A

Shortest Path in Unweighted Graph (represented using Adjacency List) using BFS

Every vertex (or node) in the graph has an adjacency list that describes the set of its neighbors.

Graph using adjacency List

In our program, we represent every node as a class object with the following attributes:

  • neighbors – Adjacency list to store neighbor nodes.
  • name – Name of the node.
  • visited – To mark the node has been visited.
  • prev – For storing the reference to the preceding node.

Here is the implementation of the algorithm for the above given unweighted graph in C++, Java and 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()

C++

#include <iostream>
#include <queue>
#include<list>
using namespace std;
 
//class representing node of a graph
class Node{
public:
  //Adjacency List of the vertex
  list<Node*> neighbors;
  char name;
  bool visited =  false;
  Node* prev = nullptr;
 
  Node(char name){ this->name = name;}
 
  //Method to connect vertices
  void addNeighbour(Node* v){
      this->neighbors.push_back(v);
      v->neighbors.push_back(this);
  }
};
 
class BFS{
  Node* start;
  Node* end;

public:
  BFS(Node* start, Node* end){
    this->start = start;
    this->end = end;
  }

  void findPath(){
    //Create queue and declare variables
    queue<Node*> Queue;
    bool reached_end = false;
    //Visit start node and add to queue
    start->visited = true;
    Queue.push(start);

    //BFS until queue is empty
    while(!Queue.empty() && !reached_end){
      //Pop a node from queue for search operation
      Node* current_node=Queue.front();
      Queue.pop();
      //Loop through neighbors nodes to find the 'end' node
      for(Node* node: current_node->neighbors){
        if(!node->visited){
          //Visit and add neighbor nodes to the queue
          node->visited= true;
          Queue.push(node);
          node->prev = current_node;
          //stop BFS if the end node is found
          if(node == end){
            reached_end = true;
            break;
          }
        }
      }
    }
    trace_route();
  }

  //Function to trace back route
  void trace_route(){
    list<Node*> route;
    Node* node = end;
    //start.prev is always null 
    //so loop until node->prev is null to trace route
    while(node != nullptr){
      route.push_front(node);
      node = node->prev;
    }

    //Display the route
    for(Node* n: route){
      cout << n->name <<" ";
    }
  }

 };

int main()
{
  //create nodes
  Node node_A('A'), node_B('B'), node_C('C'), node_D('D'), node_E('E');
  //connect nodes (i.e. create graph)
  node_A.addNeighbour(&node_B);
  node_B.addNeighbour(&node_C);
  node_C.addNeighbour(&node_C);
  node_D.addNeighbour(&node_D);
  node_B.addNeighbour(&node_E);
  
  //Driver Code
  BFS bfs(&node_A, &node_E);
  bfs.findPath();
}

Java

import java.util.*;

//Class representing graph nodes
class Node{
  String name;
  List<Node> neighbors;
  boolean visited = false;
  Node prev = null;

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

  //Method to connect nodes
  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;
  }

  public void bfs(){
    //Create queue
    Queue<Node> queue = new LinkedList<>();

    //Visit and add start node to the queue
    start.visited = true;
    queue.add(start);

    //BFS until queue is empty and not reached to the end node
    while(!queue.isEmpty()){
      //pop a node from queue for search operation
      Node current_node = queue.poll();
      //Loop through neighbors node to find the 'end'
      for(Node node: current_node.neighbors){
        if(!node.visited){
          //Visit and add the node to the queue
          node.visited =true;
          queue.add(node);
          //update its precedings nodes
          node.prev = current_node;
          //If reached the end node then stop BFS
          if(node==end){
            queue.clear();
            break;
          }
        }
      }
    }
    trace_route();
  }

  //Function to trace the route using preceding nodes
  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]

Since we are generating the route from end node to the start node, we have to reverse the route list to correct its order.

Shortest Path in Unweighted Graph (represented using Adjacency Matrix) using BFS

Adjacency Matrix is an 2D array that indicates whether the pair of nodes are adjacent or not in the graph.

Since we are representing the graph using an adjacency matrix, it will be best to also mark visited nodes and store preceding nodes using arrays.

Here are the implementations of the algorithm for the above given unweighted graph using BFS in Python, C++ and Java:

Python

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

  def bfs(self):
    queue = []
    #Visit and add the start node to the queue
    visited[self.start] = 1
    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
      #add unvisited neighbors to the queue
      while self.unvisitedNeighbor(current_node) != -1:
        neighbor_node = self.unvisitedNeighbor(current_node)
        #Visit and add neighbor nodes to the queue
        visited[neighbor_node] = 1;
        queue.append(neighbor_node);
        #update preceding node
        prev[neighbor_node] = current_node;
        #stop BFS if the end node is found
        if neighbor_node == self.end:
          queue.clear()
          break

    #BFS completed, now trace the route    
    self.trace_route()

  #Function returns the index of unvisited neighbors
  def unvisitedNeighbor(self, index):
    for i in range(len(nodes_names)):
      if adjacencyM[index][i] == 1 and visited[i] == 0:
        return i
    return -1


  #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 != -1:
      route.append(nodes_names[node])
      node = prev[node]
    #reverse the route bring start to the front
    route.reverse()
    #output route
    print(route)
    
if __name__ == '__main__':
  #vertices or nodes
  nodes_names = ['A', 'B', 'C', 'D', 'E'];
  #Adjacency Matrix
  adjacencyM = [[0, 1, 0, 0, 0],
                [1, 0, 1, 0, 1],
                [0, 1, 0, 1, 1],
                [0, 0, 1 ,0, 1],
                [0, 1, 0, 1, 0]];
  #List to mark visited nodes
  visited = [0 for x in range(len(nodes_names))]
  #List to stores preceding nodes
  prev = [-1 for x in range(len(nodes_names))]

  #Driver code
  sp = ShortestPath(0, 4)
  sp.bfs()

C++

#include <iostream>
#include <queue>
#include<list>
#define N 6
using namespace std;

//vertices or nodes
char  nodes_name[] = {'A', 'B', 'C', 'D', 'E'};
//Adjacency Matrix
int adjacencyM[N][N] = {{0, 1, 0, 0, 0},
                        {1, 0, 1, 0, 1},
                        {0, 1, 0, 1, 1},
                        {0, 0, 1 ,0, 1},
                        {0, 1, 0, 1, 0}};
 
class ShortestPath{
  //array to store preceding nodes
  int prev[N] = {-1};
  //array mapping to make visited vertices 
  int visited[N] = {0};
  //start and end nodes index
  int start, end;

public:
  ShortestPath(int start, int end){
    this->start = start;
    this->end = end;
  }

  void bfs(){
    //Create queue
    queue<int> Queue;
    //To know whether reached, so that can stop BFS
    bool reached_end = false;
    //Visit start node and add to queue
    visited[start] = 1;
    Queue.push(start);

    //BFS until queue is empty
    while(!Queue.empty() && !reached_end){
      //Pop a node from queue for search operation
      int current_node=Queue.front();
      Queue.pop();
      //Loop through neighbors nodes to find the 'end' node
      //add unvisited connected nodes to the queue
      int neighbor_node;
      while((neighbor_node =unvisitedNeighbor(current_node)) != -1){
        //Visit and add neighbor nodes to the queue
        visited[neighbor_node] = 1;
        Queue.push(neighbor_node);
        //update preceding node
        prev[neighbor_node] = current_node;
        //stop BFS if the end node is found
          if(neighbor_node == end){
            reached_end = true;
            break;
          }
      }
      
    }
    trace_route();
  }

  //Function returns index of unvisited connected vertices
  int unvisitedNeighbor(int index){
    for(int i=0; i<N; i++){
      if(adjacencyM[index][i] == 1 && (visited[i] == 0)){
        return i;
      }
    }
    return -1;
  }

  //Function to trace back route
  void trace_route(){
    list<char> route;
    int node = end;
    //start node has no preceding node
    //so loop until prev[node] is -1 
    while(node != -1){
      route.push_front(nodes_name[node]);
      node = prev[node];
    }
    //Display the route
    for(char n: route){
      cout << n <<" ";
    }
  }
 };

int main()
{
  //Driver Code
  ShortestPath shortestPath(0, 4);
  shortestPath.bfs();
}

Java

import java.util.*;

class ShortestPath{
  int adjacencyM[][];
  char nodes[];
  int prev[];
  int visited[];
  int start, end;
 
  ShortestPath(int adjacencyM[][], char[] nodes, int start, int end){
    this.adjacencyM = adjacencyM;
    this.nodes = nodes;
    this.start = start;
    this.end = end;
    //array mapping to make visited vertices 
    this.visited = new int[nodes.length];
    //array to store preceding nodes
    this.prev = new int[nodes.length];
    Arrays.fill(this.prev, -1);
  }
 
  public void bfs(){
    //Create queue
    Queue<Integer> queue = new LinkedList<>();
    //Visit and add start node to the queue
    visited[start] = 1;
    queue.add(start);
    //BFS until queue is empty
    while(!queue.isEmpty()){
      //Pop a node from the queue for search
      int current_node = queue.poll();
      //Loop through neighbors nodes to find the 'end' node
      int neighbor_node;
      while((neighbor_node =unvisitedNeighbor(current_node)) != -1){
        //visit and add neighbors nodes to the queue
        visited[neighbor_node] = 1;
        queue.add(neighbor_node);
        //update its preceding node
        prev[neighbor_node] = current_node;
        //End BFS if the end node is found
        if(neighbor_node==end){
          queue.clear();
          break;
        }
      }
    }
    //BFS complete, now trace route
    trace_route();
  }
 
  //Function returns index of unvisited neighbors
  private int unvisitedNeighbor(int index){
    for(int i=0; i<adjacencyM.length; i++){
      if(adjacencyM[index][i] == 1 && visited[i] == 0){
        return i;
      }
    }
    return -1;
  }

  //Function to trace route using preceding nodes
  private void trace_route(){
    int node = end;
    List<Character> route = new ArrayList<>();
    //start node has no preceding node
    //so loop until prev[node] is -1 
    while(node!=-1){
      route.add(nodes[node]);
      node = prev[node];
    }
    //Reverse route to bring start at front
    Collections.reverse(route);
    //Output the route
    System.out.println(route);
  }
}
 
class Main {
  public static void main(String[] args) {
    //vertices or nodes array
    char nodes[] = {'A', 'B', 'C', 'D', 'E'};
    //Adjacency Matrix
    int adjacencyM[][] = {{0, 1, 0, 0, 0},
                          {1, 0, 1, 0, 1},
                          {0, 1, 0, 1, 1},
                          {0, 0, 1 ,0, 1},
                          {0, 1, 0, 1, 0}};
    //Driver Code
    ShortestPath shortestPath = new ShortestPath(adjacencyM, nodes, 0, 4);
    shortestPath.bfs();
    
  }
}

Output:

[A, B, E]

The worst-case time complexity of the discussed methods is equivalent to the time complexity of the BFS algorithm i.e. O(V+E), where V and E respectively are the numbers of vertices (nodes) and edges of the given graph.

In this tutorial, we learned to find the shortest path in an unweighted graph using the BFS algorithm with Python, C++ and Java programming languages.

Leave a Reply

Your email address will not be published. Required fields are marked *