<p>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.</p>

CC BY-SA 3.0
2013-01-28T23:43:06.723Z
Do you mean a lower bound on _the time complexity of_ SSSP?
Jeffε
CC BY-SA 3.0
2013-01-29T09:21:31.073Z
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
CC BY-SA 3.0
2013-01-29T10:12:24.810Z
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
CC BY-SA 3.0
2013-01-29T11:33:32.730Z
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
CC BY-SA 3.0
2013-01-29T15:31:21.903Z
@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ε
CC BY-SA 3.0
2013-01-30T13:52:42.963Z
Right, I always make that mistake...
adrianN
CC BY-SA 4.0
2020-08-31T21:53:20.273Z
@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
<graph-theory><graph-algorithms><lower-bounds><reductions><decision-trees>
Is there a tight lower bound on the complexity of SSSP on a graph?
user1278599
# Is there a tight lower bound on the complexity of SSSP on a graph?

(Asked by: username_0 on 2013-01-28)

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.

**Tags:** graph-theory, graph-algorithms, lower-bounds, reductions, decision-trees
> **Comments:**
> **username_1**: Do you mean a lower bound on _the time complexity of_ SSSP?  
> **username_2**: 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).  
> **username_0**: 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)?  
> **username_2**: 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.  
> **username_1**: @adrianN: You mean Ω(m), not O(n).  You have to consider every edge, and O(...) means "**at most** a constant times..." not "**at least**..."  
> **username_2**: Right, I always make that mistake...  
> **username_3**: @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.  

---

## 0 answers

