Are there any non-trivial lower bounds on the complexity of single-source shortest paths (SSSP) in a directed graph, where all edges have non-negative edge weights? Can we rule out the possibility of an algorithm with $O(n+m)$ running time? Are there any lower bounds in any restricted models, e.g., in the decision tree model, or something like that?

Dijkstra's algorithm can be implemented to run in $O(m+n \log n)$ time, with suitable data structures. I understand Thorup has an algorithm whose running time is $O(n + m \log \log n)$ in the RAM model, and other algorithms are known in the RAM model. However, I have not found any algorithm with $O(n+m)$ running time, nor any lower bound to rule out the possibility of such an algorithm.

(I know there is a $O(n+m)$ time algorithm for undirected graphs with non-negative integer edge weights, due to Thorup, but here I am asking about directed graphs. I found Is there a tight lower bound on the complexity of SSSP on a graph?, but that is asking about undirected graphs and allows negative edge weights; I want to know about directed graphs, and am focusing on the case with non-negative edge weights.)



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.