Instance-Optimality of Bidirectional Dijkstra on Simple Graphs

Christian Bertram, Mads Vestergaard Jensen, Mikkel Thorup +2

We study the shortest-path problem on graphs with positive real-valued edge weights. Given a source vertex $s$ and a target vertex $t$, the goal is to calculate the length of the s…