Bidirectional Dijkstra’s Algorithm is Instance-Optimal
Bernhard Haeupler, Richard Hladík, Václav Rozhoň, Robert Endre Tarjan, Jakub Tětek · Society for Industrial and Applied Mathematics eBooks · 2025
While Dijkstra’s algorithm has near-optimal time complexity for the problem of finding the shortest si-path, in practice, other algorithms are often superior on huge graphs. A prominent such example is the bidirectional search, which executes Dijkstra’s algorithm from both endpoints in parallel and stops when these executions meet.