distance_product (381B)
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 7 [APSP_reduces_to_distance_product] 8 9 Computing the distance product reduces to [negative_triangle] 10 11 See also: [all_pairs_shortest_path] 12 13 Aliases: min plus product, min-plus product