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.

  • 1
    $\begingroup$ Do you mean a lower bound on the time complexity of SSSP? $\endgroup$
    – Jeffε
    Jan 28 '13 at 23:43
  • $\begingroup$ 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). $\endgroup$
    – adrianN
    Jan 29 '13 at 9:21
  • $\begingroup$ 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)? $\endgroup$ Jan 29 '13 at 10:12
  • $\begingroup$ 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. $\endgroup$
    – adrianN
    Jan 29 '13 at 11:33
  • $\begingroup$ @adrianN: You mean Ω(m), not O(n). You have to consider every edge, and O(...) means "at most a constant times..." not "at least..." $\endgroup$
    – Jeffε
    Jan 29 '13 at 15:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.