single_source_shortest_path_faster (494B)
1 # Single source shortest path faster 2 3 Solve [single_source_shortest_path] faster than [bellman_ford] 4 5 - variant: "scaling-based algorithms": O(m sqrt(n) log W) 6 - [bernstein2022negative] best paper: O(m log^8 n log W) 7 - [bringmann2023negative] improved by [log_shaving] 8 - open whether log W can be removed 9 10 recent result [bernstein2023negative] improving [bellman_ford] 11 vs [lower_bounds] on [circuit_classes] for this problem [jukna2016optimality] 12 13 Up: [single_source_shortest_path_algorithm]