Comment on Undirected SS Shortest Paths with Positive Integer Weights in O(n) (1999) [pdf]Comments−elikoga3y(requires constant-time multiplication) from https://en.wikipedia.org/wiki/Shortest_path_problem#Single-s...−elikoga3yThe $n$ in the title refers to the amount of edges.−klyrs3yYou're talking past the parent's point. If the integer weights grow faster than n*, then this algorithm will grow faster than O(n)* integer weights measured in bit-count; log factors from multiplication time ignored
Comments
(requires constant-time multiplication) from https://en.wikipedia.org/wiki/Shortest_path_problem#Single-s...
The $n$ in the title refers to the amount of edges.
You're talking past the parent's point. If the integer weights grow faster than n*, then this algorithm will grow faster than O(n)
* integer weights measured in bit-count; log factors from multiplication time ignored