# Is there a tight lower bound on the complexity of SSSP on a graph?

I'm an undergrad and I'm not sure if this is the right way to ask this question. I want to know the lower bound on single-source shortest path computation in a general graph. The graph is allowed to have negative weight edges.

• Do you mean a lower bound on the time complexity of SSSP? – Jeffε Jan 28 '13 at 23:43
• To my knowledge, only if you require that the paths be produced in order, like e.g. Dijkstra's algorithm does. Then there is the sorting lower bound. Otherwise the best lower bound is O(n). – adrianN Jan 29 '13 at 9:21
• Let me make sure I get what you say. In order means that the shorter paths come first? Also, n stands for the number of nodes? And it's a bound on the output time (we need to find the distance to all nodes)? – user1278599 Jan 29 '13 at 10:12
• Yes, consider a star with n edges (so n+1 nodes) and you want to find shortest paths starting from the center node. If your algorithm outputs short short paths first, you sort the weights on the edges. You can't do that faster than n log n in the usual machine model. – adrianN Jan 29 '13 at 11:33
• @adrianN: You mean Ω(m), not O(n). You have to consider every edge, and O(...) means "at most a constant times..." not "at least..." – Jeffε Jan 29 '13 at 15:31