distance_product (536B)
1 # Distance product 2 3 Given two [adjacency_matrices] A and B their *distance product* is 4 (A*B)[i,j ] defined to be min_k (A[i,k ] + B[k,j ]) 5 - this is [matrix_multiplication] in the [tropical_semiring] 6 - no known [subcubic_matrix_multiplication] algorithms 7 - but cf [williams2014faster], [williams2020truly]... 8 9 [APSP_reduces_to_distance_product] 10 11 Computing the distance product reduces to [negative_triangle] 12 13 See also: [all_pairs_shortest_path], [mpp_minimum] 14 15 Aliases: min plus product, min-plus product 16 17 Up: [matrix_multiplication]