single_source_shortest_path_faster_nonnegative (611B)
1 # Single source shortest path faster nonnegative 2 3 Solving [single_source_shortest_path] on [directed_graphs] with nonnegative weights faster than [Dijkstra's_algorithm] 4 5 [duan2023randomized] gives a faster algorithm but on [undirected_graphs] only 6 7 [duan2025breaking], in O(m log^{2/3} n) 8 - explained in https://www.quantamagazine.org/new-method-is-the-fastest-way-to-find-the-best-routes-20250806/ 9 - does not order the vertices by distance, just produces the distances 10 - if you have to order the vertices, [Dijkstra's_algorithm] is optimal 11 - cf [haeupler2025universal] 12 13 Up: [single_source_shortest_path]