On the Instance Optimality of Bidirectional Dijkstra's Algorithm

Abstract

Recent work by Haeupler, Hlad\'ik, Rozhon, Tarjan, and T\v{e}tek on the instance optimality of shortest-path algorithms established several results concerning Dijkstra's algorithm and bidirectional Dijkstra's algorithm in weighted and unweighted graphs. Motivated by these results, we revisit the question of instance optimality for shortest $st$-path algorithms in the standard query model. We identify several issues in the analysis of the instance optimality of both unidirectional and bidirectional Dijkstra's algorithms and provide corresponding counterexamples. We then propose a minimal simple modification of the bidirectional Dijkstra algorithm and prove that the resulting variant is instance optimal in the weighted setting. Furthermore, we revisit the unweighted case, provide a simplified proof of the lower bound showing that no algorithm can achieve instance optimality up to a factor better than $O(\Delta)$, where $\Delta$ denotes the maximum degree of the graph, and discuss the implications of this result for approximation algorithms. Finally, we make progress on the open problem of instance optimality in simple graphs. We show that if the problem instance satisfies $n\ge m/16$, where $n$ is the number of nodes and $m$ is the number of edges queried by our algorithm, then it is optimal up to a constant factor. Additionally, we show instance optimality for a broad class of instances, in particular when the largest degree in the graph is at most the square root of the number of explored edges, our algorithm exhibits optimality up to a constant factor.