wiki_research

personal research wiki
git clone https://a3nm.net/git/wiki_research/
Log | Files | Refs

all_pairs_shortest_path (1205B)

      1 # All pairs shortest path (APSP)
      2 
      3 Given a [graph], compute the [distance] between all pairs of nodes
      4 
      5 Many works have tried to shave off logs; best algorithm by [ryan_williams]: n^3/exp(sqrt(log n))
      6 
      7 Hypothesis [apsp_hypothesis]
      8 
      9 The unweighted version amounts to [transitive_closure], which can be solved by [matrix_multiplication]
     10 - also some algorithms for small weights
     11 - APSP is [matrix_multiplication] but on [tropical_semiring], see [distance_product]
     12 
     13 APSP can be expressed in [datalog] with the right kind of [aggregation], in linear or binary form
     14 
     15 Algorithm: [floyd_warshall_algorithm]
     16 
     17 Reduction to [distance_product]
     18 
     19 [johnsons_algorithm]: in O(mn) we can transform to remove the negative weights
     20 
     21 connection between APSP and [distance_product] ([matrix_multiplication] in [semiring_tropical]), like for [reachability_all_pairs]: running times are the same up to log factors
     22 - and with [negative_triangle]: one is subcubic iff the other is
     23 
     24 Approximation: [all_pairs_shortest_path_approximate]
     25 
     26 Beware: APSP can also mean "All pairs suffix prefix", cf [gusfield1992efficient], [zuba2024approximate]
     27 
     28 Up: [shortest_path], [fine_grained_complexity_problems]
     29 
     30 See also: [reachability_all_pairs]