from Hacker News

Undirected SS Shortest Paths with Positive Integer Weights in O(n) (1999) [pdf]

by cpp_frog on 6/5/23, 1:16 PM with 7 comments

  • by elikoga on 6/6/23, 1:31 PM

    (requires constant-time multiplication) from https://en.wikipedia.org/wiki/Shortest_path_problem#Single-s...

  • by mihaic on 6/6/23, 2:07 PM

    Quite unexpected. Does anyone have a summary somewhere? I don't fully understand the bucketing approach and my 2023 attention span can't handle reading the whole paper.

  • by p0w3n3d on 6/7/23, 8:58 AM

    I understand there are limits on the title length, but SS? Really?