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?
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.