Adding Bidirectional dijkstra

[sha0urya]

Is your feature request related to a problem? Please describe. A clear and concise description of what the problem is.?

Bidirectional Dijkstra is an algorithm that finds the shortest path between two nodes in a graph by simultaneously searching from both the source and target nodes. By exploring the graph from both ends, it reduces the search space and can be more efficient than the traditional Dijkstra's algorithm, especially for large graphs or extensive search spaces.

Describe the solution you'd like

I want to implement this algorithm in C, C++, Java and Python.

Please assign me under SSOC'23.

[Kumar-laxmi]

Please elaborate your explanation with diagrams and examples

[sha0urya]

Sure! The Bidirectional Dijkstra's algorithm is an optimized version of the classical Dijkstra's algorithm for finding the shortest path between two vertices in a graph. Instead of exploring the graph from a single source vertex, Bidirectional Dijkstra's algorithm simultaneously explores the graph from both the source and destination vertices, aiming to meet in the middle and reduce the overall search space.

To explain Bidirectional Dijkstra's algorithm, let's consider the following example graph:

   A ---5--- B
  /|\      /|\
 4 | \     | 2
  \|  \    |/
   C --1-- D

In this example, we want to find the shortest path from vertex A to vertex D using Bidirectional Dijkstra's algorithm.

The algorithm works as follows:

1. Initialize two priority queues, one for the forward search (starting from A) and one for the backward search (starting from D). Also, initialize two distance arrays, one for the forward search and one for the backward search. Set the initial distances of all vertices to infinity, except for the source vertex, which is set to 0.

Forward queue: [A]
Forward distance: [0, infinity, infinity, infinity]
Backward queue: [D]
Backward distance: [infinity, infinity, infinity, 0]

2. While both queues are not empty, perform the following steps:

   a. Choose the vertex with the minimum distance from the forward queue and remove it. Let's call this vertex "current".

   b. For each neighbor of "current" in the forward graph, calculate the tentative distance by adding the weight of the edge between "current" and its neighbor to the distance of "current". If the tentative distance is smaller than the current distance of the neighbor, update the distance and add the neighbor to the forward queue.

   c. If the current vertex is reached by the backward search (i.e., its distance in the backward distance array is not infinity), calculate the total distance from the source to the destination by summing the forward and backward distances. If it is smaller than the current best distance, update the best distance and the best meeting point.

   d. Repeat steps a, b, and c for the backward queue, considering neighbors in the backward graph.

3. Once the queues meet (i.e., a vertex is encountered by both searches), the algorithm terminates. The best meeting point found during the search corresponds to the middle of the shortest path.

Let's illustrate the steps of the algorithm using the example graph:

1. Initialization:

   • Forward queue: [A]
   • Forward distance: [0, infinity, infinity, infinity]
   • Backward queue: [D]
   • Backward distance: [infinity, infinity, infinity, 0]

2. Iteration 1:

   • Choose "A" from the forward queue.

   • Update the distance of "B" to 5 (0 + 5) and add it to the forward queue.

   • No meeting point is found.

   • Choose "D" from the backward queue.

   • Update the distance of "C" to 1 (0 + 1) and add it to the backward queue.

   • No meeting point is found.

3. Iteration 2:

   • Choose "B" from the forward queue.

   • Update the distance of "D" to 7 (5 + 2) and add it to the forward queue.

   • No meeting point is found.

   • Choose "C" from the backward queue.

   • Update the distance of "A" to 5 (1 + 4) and add it to the backward queue.

   • Meeting point found!

Total distance from A to D is 10.

4. Termination:
   • Best meeting point: C (total distance = 10)

By backtracking from the meeting point, we can construct the shortest path from A to D: A -> C -> D.

The key idea of Bidirectional Dijkstra's algorithm is to explore the graph simultaneously from both ends, reducing the overall search space and improving efficiency. It is particularly useful in scenarios where the search space is vast, and the graph is large.

I hope this explanation helps! Let me know if you have any further questions.

[github-actions[bot]]

Stale issue message