3

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.

user1278599
  • 31
  • 2
  • 1
    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 09: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
  • Right, I always make that mistake... – adrianN Jan 30 '13 at 13:52
  • @adrianN: I think your lower bound doesn't work if the algorithm just has to e.g. return the shortest path tree which is always a star in your case. In general if the graph has only $O(n)$ edges, there are only $2^{O(n)}$ possible spanning trees, so you can't get an easy comparison-based lower bound like for sorting. – Aviad Rubinstein Aug 31 '20 at 21:53

0 Answers0