This thesis explores various approaches to solving the SSSP problem, beginning with classical algorithms such as Dijkstra’s algorithm and the Bellman-Ford algorithm, and extending to Yen’s algorithm and the Randomized "Bundle Dijkstra" algorithm. Special focus is given to the role of adaptivity in accelerating computations.

Beyond algorithmic techniques, the thesis delves into the theoretical limits of relaxation-based SSSP algorithms, analyzing lower bounds on the number of required edge relaxations for determinisitc non-adaptive algorithms and upper bounds for randomized adaptive algorithms. Especially with the new results proving that any deterministic non-adaptive relaxation algorithm requires at least 1/2n³ relaxations in the worst case, it closes the gap with Yen’s improvement to Bellman-Ford, indicating the algorithm's optimality within the class.

Finally, the thesis explores the hardness of the problem of determining whether a given sequence of relaxations correctly computes all shortest path distances, which is shown to be co-NP-complete. It formalizes the idea that precomputing a “universal” relaxation sequence that works for all graphs is provably hard. And there is no efficient algorithm (in polynomial time) known to verify whether an arbitrary relaxation sequence is valid, unless P = NP.