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.)
