Bidirectional Dijkstra's Algorithm is Instance-Optimal
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915340968001536 |
|---|---|
| author | Haeupler, Bernhard Hladík, Richard Rozhon, Vaclav Tarjan, Robert E. Tětek, Jakub |
| author_facet | Haeupler, Bernhard Hladík, Richard Rozhon, Vaclav Tarjan, Robert E. Tětek, Jakub |
| contents | Although Dijkstra's algorithm has near-optimal time complexity for the problem of finding a shortest path from a given vertex $s$ to a given vertex $t$, in practice other algorithms are often superior on huge graphs. A prominent example is bidirectional search, which concurrently executes Dijkstra's algorithm forward from $s$ and backward from $t$, and stops when these executions meet.
In this paper, we give a strong theoretical justification for the use of bidirectional search to find a shortest $st$-path. We prove that for weighted multigraphs, both directed and undirected, a careful implementation of bidirectional search is instance-optimal with respect to the number of edges it examines. That is, we prove that no correct algorithm can outperform our implementation of bidirectional search on any single instance by more than a constant factor.
For unweighted graphs, we show that bidirectional breadth-first search is instance-optimal up to a factor of $O(Δ)$ where $Δ$ is the maximum degree of the graph. We also show that this is best possible. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_14638 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Bidirectional Dijkstra's Algorithm is Instance-Optimal Haeupler, Bernhard Hladík, Richard Rozhon, Vaclav Tarjan, Robert E. Tětek, Jakub Data Structures and Algorithms F.2.2; G.2.2 Although Dijkstra's algorithm has near-optimal time complexity for the problem of finding a shortest path from a given vertex $s$ to a given vertex $t$, in practice other algorithms are often superior on huge graphs. A prominent example is bidirectional search, which concurrently executes Dijkstra's algorithm forward from $s$ and backward from $t$, and stops when these executions meet. In this paper, we give a strong theoretical justification for the use of bidirectional search to find a shortest $st$-path. We prove that for weighted multigraphs, both directed and undirected, a careful implementation of bidirectional search is instance-optimal with respect to the number of edges it examines. That is, we prove that no correct algorithm can outperform our implementation of bidirectional search on any single instance by more than a constant factor. For unweighted graphs, we show that bidirectional breadth-first search is instance-optimal up to a factor of $O(Δ)$ where $Δ$ is the maximum degree of the graph. We also show that this is best possible. |
| title | Bidirectional Dijkstra's Algorithm is Instance-Optimal |
| topic | Data Structures and Algorithms F.2.2; G.2.2 |
| url | https://arxiv.org/abs/2410.14638 |