Understanding Bidirectional Dijkstra’s Algorithm

Photo by Florian Steciuk on Unsplash

Dijkstra’s algorithm is well known shortest path finding algorithm in a graph. But there exists Bidirectional Dijkstra algorithm as well which runs two simultaneous searches, one in the forward direction from source and the other in the backward direction from destination until they meet eventually. In this article, we will cover the algorithm with an example and implement it in Java Language.

Introduction

The algorithm appears to be complex at the beginning but once you get the picture it’s quite simple actually. Assume the graph G with vertices V and edges E. Also, imagine that there is another Graph G’ which has all the edges in G reversed. Now let’s start the search from source vertex G and destination vertex in G’ simultaneously till the search spaces meet. With this approach, search space is reduced to nearly a factor of 2.

Algorithm

• Like Dijkstra’s algorithm, start search from source vertex u in G and destination vertex v in G’
• Maintain DistanceF,DistanceB map for storing min distances of vertices from u and v respectively initialised to ∞
• Lets maintain priority Queues QueueF for forward and QueueB for backward searches
• Let there be a Join Node which are vertices found common in forward…