Conditional lower bounds on the running time of the single source shortest path problem

Question

Just out of curiosity, I was wondering whether there is a conditional lower-bound on the running time of an algorithm for the Single Source Shortest Path Problem (on directed or undirected graphs). I found papers with lower-bounds on some special models of computing such as PRAM or distributed systems but I was wondering if there is a well-known lower-bound based on the 3-sum, SETH or these kinds of conjectures.

Answer 1

I found a lower-bound on the decremental SSSP based on the online matrix vector hypothesis. Decremental SSSP is a dynamic version of SSSP where updates are edge-deletions. On the other hand, it is appearing clear to me, that typical conditional lower-bounds do not make sense for SSSP, since relevant conjectures show that the exponent can not be improved and do not exclude improvement of log factors. On the other hand, improving the exponent in SSSP means a sublinear algorithm which is excluded since the size of the input is a lower-bound on the running time of any problem.