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.
Is there a tight lower bound on the complexity of SSSP on a graph?
graph theory;graph algorithms;lower bounds;reductions;decision trees