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

C++

Java

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

C++

Java

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