Termination condition
Stop when top of both PQs sum ≥ best path found through meeting node. Care needed — meeting node isn't always the top!
Advertisement
Speedup analysis
Search explores ~O(V^(d/D)) where d = distance, D = diameter. Bidirectional: 2 × O(V^(d/(2D))). Massive for large graphs.
Advertisement
Backward search
Directed graphs: reverse edges. Undirected: same graph, different frontier.
Applications
Road routing. Public transit. Any point-to-point on huge graph. Base of most modern route planners.