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.

worked-example

Consider a simple trap graph with vertices V = {0, 1, 2, 3} and source s=0, target t=3. The edges are: (0,3) with weight 10, (0,1) with weight 1, (1,3) with weight 1, (1,2) with weight 2, and (2,3) with weight 2. In the first expansion from s, the forward search sees vertex 3 with tentative distance d_F(3) = 10. The backward search from t also sees vertex 3 with d_B(3) = 0.

Forward queue: (0,0) → Expand 0. d_F(1)=1, d_F(3)=10. Queue: (1,1), (10,3).
Backward queue: (0,3) → Expand 3. d_B(0)=10, d_B(1)=1, d_B(2)=2. Queue: (1,1), (2,2), (10,0).
The first meeting occurs at vertex 3, producing a first candidate path of length 10 + 0 = 10.
If the algorithm stopped here, it would return 10. However, the actual shortest path is 0 → 1 → 3 with total length 1+1=2.
The algorithm must continue. The next expansions (e.g. forward expanding 1) update the best candidate to d_F(1) + d_B(1) = 1 + 1 = 2.
The stopping condition min(q_F) + min(q_B) ≥ text(bestCandidate) ensures no shorter path exists. Once the minimum distances in both queues sum to at least 2, the search terminates safely.

experiment

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

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

limitations

The bidirectional Dijkstra algorithm assumes all edge weights are non-negative. If negative weights are present, the distance estimates used in the stopping condition are no longer valid lower bounds, and the algorithm may terminate prematurely or fail to find the optimal path. The described stopping certificate also assumes that the heuristic (in this case, zero) is consistent. Furthermore, in highly asymmetric graphs (where one direction has a significantly higher branching factor than the other), bidirectional search might not provide a substantial speedup over unidirectional search if the search frontiers do not meet efficiently near the middle of the path.

references

The theoretical foundations and stopping criteria for bidirectional search, particularly the necessity of continuing search after the first intersection, are discussed in the literature on heuristic search.
Reference: Computing the Shortest Path: A Search Meets Graph Theory

Bidirectional Dijkstra Frontier Stop Certificate