Bidirectional Dijkstra's Algorithm is Instance-Optimal

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