wiki_research

commit f9937d8dfe330e280724dae627543873e9a218df
parent e6809d435306eaef0dfed7423590cfba0b3661a0
Author: Antoine Amarilli <a3nm@a3nm.net>
Date:   Fri, 22 Aug 2025 14:44:17 +0200

Merge branch 'master' of a3nm.net:git/wiki_research

Diffstat:
single_source_shortest_path
 | 
3
++-
single_source_shortest_path_faster
 | 
2
++
single_source_shortest_path_faster_nonnegative
 | 
13
+++++++++++++

3 files changed, 17 insertions(+), 1 deletion(-)
diff --git a/single_source_shortest_path b/single_source_shortest_path
@@ -1,6 +1,7 @@
 # Shortest path single source
 
 - [single_source_shortest_path_algorithm]
-  - [single_source_shortest_path_faster]
+  - [single_source_shortest_path_faster] (relative to [bellman_ford])
+  - [single_source_shortest_path_faster_nonnegative] (relative to [dijkstra's_algorithm])
 
 Up: [shortest_path]
diff --git a/single_source_shortest_path_faster b/single_source_shortest_path_faster
@@ -11,3 +11,5 @@ recent result [bernstein2023negative] improving [bellman_ford]
 vs [lower_bounds] on [circuit_classes] for this problem [jukna2016optimality]
 
 Up: [single_source_shortest_path_algorithm]
+
+See also: [single_source_shortest_path_faster_nonnegative]
diff --git a/single_source_shortest_path_faster_nonnegative b/single_source_shortest_path_faster_nonnegative
@@ -0,0 +1,13 @@
+# Single source shortest path faster nonnegative
+
+Solving [single_source_shortest_path] on [directed_graphs] with nonnegative weights faster than [Dijkstra's_algorithm]
+
+[duan2023randomized] gives a faster algorithm but on [undirected_graphs] only
+
+[duan2025breaking], in O(m log^{2/3} n)
+- explained in https://www.quantamagazine.org/new-method-is-the-fastest-way-to-find-the-best-routes-20250806/
+- does not order the vertices by distance, just produces the distances
+  - if you have to order the vertices, [Dijkstra's_algorithm] is optimal
+    - cf [haeupler2025universal]
+
+Up: [single_source_shortest_path]