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?