# Bounded Integer Edge Weights, Dijkstra's Algorithm

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?

## 1 Answer

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.

• 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. – ZeroUltimax Feb 8 '17 at 17:10
• 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! – Nyfiken Gul Feb 9 '17 at 8:35