Comment on Undirected SS Shortest Paths with Positive Integer Weights in O(n) (1999) [pdf]parentComments−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
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