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

by cpp_frogon 6/5/2023, 1:16:48 PM with 3 comments
  • by elikogaon 6/6/2023, 1:31:35 PM

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

  • by mihaicon 6/6/2023, 2:07:06 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 p0w3n3don 6/7/2023, 8:58:59 AM

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