3
$\begingroup$

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.

$\endgroup$
7
  • 1
    $\begingroup$ Do you mean a lower bound on the time complexity of SSSP? $\endgroup$
    – Jeffε
    Jan 28, 2013 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, 2013 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, 2013 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, 2013 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, 2013 at 15:31

0

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.