News for hackers. Stuff that matters.
Re:Negative-Weight Single-Source Shortest Paths in Near-Line... by lambo4bkfast on Sunday January 22, 2023 @06:08PM (#34483339)
From the paper:

"Two textbook algorithms for SSSP are Bellman-Ford and Dijkstra’s algorithm. Dijkstra’s algorithm is near-linear time (O(m + n log n) time)"

This is incorrect; Dijkstra's Algorithm using a binary priority queue has: O((m + n)log n) time

Re:Negative-Weight Single-Source Shortest Paths in Near-Line... by cashweaver on Sunday January 22, 2023 @06:18PM (#34483428)
I recall that the quoted time complexity is correct, assuming the queue is a Fibonacci heap.

https://en.m.wikipedia.org/wiki/Dijkstra%27s_algorithm#CITER...

Re:Negative-Weight Single-Source Shortest Paths in Near-Line... by lambo4bkfast on Sunday January 22, 2023 @06:26PM (#34483492)
Ah yes you're correct. Fibonacci heap's aren't usually used in most applications of dijkstra's algorithm (such as road networks) though because trading an O(logn) heap.decrease_key operation for an O(1) heap.decrease_key operation, but getting a slower heap.delete_min operation (by a constant factor) isn't worth it.

This is because there are much fewer heap.decrease_key operations on average than Dijkstra's worst case analysis suggests. The expected number of heap.decrease_key operations is not large enough to offset the loss in average runtime for the heap.delete_min operation.

Re:Negative-Weight Single-Source Shortest Paths in Near-Line... by cashweaver on Sunday January 22, 2023 @06:27PM (#34483497)
I didn't know that! Thank you for elaborating.