[HN Gopher] Undirected SS Shortest Paths with Positive Integer W...
___________________________________________________________________
Undirected SS Shortest Paths with Positive Integer Weights in O(n)
(1999) [pdf]
Author : cpp_frog
Score : 42 points
Date : 2023-06-05 13:16 UTC (1 days ago)
(HTM) web link (www.csie.ntu.edu.tw)
(TXT) w3m dump (www.csie.ntu.edu.tw)
| mihaic wrote:
| 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 wrote:
| 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.
| [deleted]
| elikoga wrote:
| (requires constant-time multiplication) from
| https://en.wikipedia.org/wiki/Shortest_path_problem#Single-s...
| elikoga wrote:
| The $n$ in the title refers to the amount of edges.
| klyrs wrote:
| 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
___________________________________________________________________
(page generated 2023-06-06 23:01 UTC)