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

49 points by cpp_frog 2 years ago | 7 comments
  • elikoga 2 years ago
    (requires constant-time multiplication) from https://en.wikipedia.org/wiki/Shortest_path_problem#Single-s...
    • elikoga 2 years ago
      The $n$ in the title refers to the amount of edges.
      • klyrs 2 years 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

    • mihaic 2 years ago
      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.
      • alpaca128 2 years ago
        It looks like they replaced the usual sorting step in Dijkstra's algorithm (used for selecting the next node) with the first step of bucket sort in which the values are distributed across a fixed number of buckets. This can be done in linear time but requires integer values. Then they just skip the second step, which is sorting within each bucket, and pick an arbitrary element from the lowest-cost bucket. And I think one of the proofs shows that this incomplete sorting is correct for this use-case.

        I didn't get the formal details either, though, so correct me if I'm wrong.

        • mihaic 2 years ago
          That was my understanding as well, thanks.

          You'd pretty much have to make sure that no two nodes from the same bucket can improve on one another, and I can't really understand how you'd pick the bucketing so you don't need O(MaxLength) buckets.

        • 2 years ago
        • p0w3n3d 2 years ago
          I understand there are limits on the title length, but SS? Really?