0
$\begingroup$

I'm trying to understand how we can get the time complexity of Dijkstra's Algorithm down from O(V²) (for a matrix-implemented Dijkstra's) to O(V) if the edge weights of our graph are bounded by a constant C. I've read up on this MIT lecture but can't really wrap my head around the explanation.

It says that all paths are less than (|V|-1) * C, but why can't they be equal to (|V|-1) * C? For example, if the graph has one edge between each node and the weight on every node is C. Shouldnt it be less than or equal to?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
0
$\begingroup$

In the case of your example, the shortest path is of length C since all paths are 1 edge long; there is an edge between each pair of node.

The figure of (|V|-1)C comes from the situation where all your nodes form a single chain, with edge weights of C. Then, the path between the first and last node on the chain is of length (|V|-1)C.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ I should add that this difference of -1 doesn't affect the complexity analysis, so if there's something else you don't understand, you might want to post another question. $\endgroup$
    – ZeroUltimax
    Feb 8, 2017 at 17:10
  • $\begingroup$ Thanks a bunch! That's what I thought aswell, but on the lecture it says that all paths are strictly less than (|V|-1)*C.. Well, I guess I should just take it as less or equal to then, thanks again! $\endgroup$
    – Nyfiken Gul
    Feb 9, 2017 at 8:35

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.