Y
Hacker News
new
|
ask
|
show
|
jobs
by
elikoga
1103 days ago
(requires constant-time multiplication) from
https://en.wikipedia.org/wiki/Shortest_path_problem#Single-s...
1 comments
elikoga
1103 days ago
The $n$ in the title refers to the amount of edges.
link
klyrs
1103 days ago
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
link