Bidirectional Dijkstra Frontier Stop Certificate

When computing the shortest path from a source vertex s to a target vertex t, bidirectional search runs two simultaneous search procedures: one forward from s on the original graph edges, and one backward from t on the reversed edges. A common misconception is that the algorithm can immediately terminate and return the path when the two search frontiers first meet (i.e., when a vertex is scanned by both searches). While this vertex forms a valid candidate path, it is not necessarily the shortest one. A stopping certificate is required to safely terminate the algorithm and guarantee optimality.

experiment

You can test the first-candidate trap and the stopping condition in the interactive module at Bidirectional Dijkstra Frontier Stop Certificate.

1. Select the Graph control to "Shortcut trap".
2. Set Source to "0" and Target to "3".
3. Set Inspected expansions to "10" to allow the algorithm to run to completion.
4. Observe that the First candidate is 10, which represents the direct path (0,3), but the Final distance is correctly 2.
5. Decrease the Inspected expansions to see the state of the queues and the best candidate at intermediate steps.