commit 5f557c0520a1deffe36ae099e3dbf37aed271488
parent 73fc832a9fbc86b65133fefafddbe88092065411
Author: Antoine Amarilli <a3nm@a3nm.net>
Date: Thu, 21 Aug 2025 09:08:53 +0200
commit with codex
Diffstat:
1 file changed, 5 insertions(+), 0 deletions(-)
diff --git a/single_source_shortest_path_faster_nonnegative b/single_source_shortest_path_faster_nonnegative
@@ -2,7 +2,12 @@
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]
