## 4 APSP and Routing Tables
### Distance Products via Triangle Finding  
Having established reductions to distance products, we turn to their efficient computation. The main idea is that we can reduce distance products to a binary search in which each step in the search finds negative triangles. This procedure corresponds to ([18] Proposition 2), which we describe here, restricting to finding the distance product square needed for Equation (2).  
A negative triangle in a weighted graph is a set of edges \(\Delta^{-}=(uv,vw,wu)\subset E^{3}\), such that \(\sum_{e\in\Delta^{-}}W_{e}<0\). Let us denote the set of all negative triangles in a graph \(G\) as \(\Delta^{-}_{G}\). Specifically, we will be interested in each node \(v\) being able to output edges \(vu\in\delta(v)\), such that \(vu\) is involved in at least one negative triangle in \(G\). Let us call this problem FindEdges, and define it formally as follows:FindEdges  
Input: An integer-weighted (directed or undirected) graph \(G=(V,E,W)\) distributed among the nodes, with each node \(v\) knowing \(\mathcal{N}_{G}(v)\), as well as the weights \(W_{vu}\) for each \(u\in\mathcal{N}_{G}(v)\). Output: For each node \(v\), its output is all the edges \(vu\in E\) that are involved in at least one negative triangle in \(G\).  
Proposition 1: _If FindEdges on an \(n\)-node integer-weighted graph \(G=(V,E,W)\) can be solved in \(T(n)\) rounds, then the distance product \(A\star B\) of two \(n\times n\) matrices \(A\) and \(B\) with entries in \([M]\) can be computed in \(T(3n)\cdot\lceil\log_{2}(2M)\rceil\) rounds._  
Proof: Let \(A\) and \(B\) be arbitrary \(n\times n\) integer-valued matrices, and \(D\) be an \(n\times n\) matrix initialized to \(\mathbf{0}\). Let each \(u\in V\) simulate three copies of itself, \(u_{1},u_{2},u_{3}\), writing \(V_{1},V_{2},V_{3}\) as the sets of copies of nodes in \(V\). Consider the graph \(G^{\prime}=(V_{1}\cup V_{2}\cup V_{3},E^{\prime},W^{\prime})\), by letting \(u_{i}v_{j}\in E^{\prime}\) for \(u_{i}\in V_{i},v_{j}\in V_{j},i\
eq j\), taking \(W^{\prime}_{u_{1}v_{2}}=A_{uv}\) for \(u_{1}\in V_{1},v_{2}\in V_{2}\), \(W^{\prime}_{u_{2}v_{3}}=B_{uv}\) for \(u_{2}\in V_{2},v_{3}\in V_{3}\), and \(W^{\prime}_{u_{3}v_{1}}=D_{uv}\) for \(u_{3}\in V_{3},v_{1}\in V_{1}\). An edge \(zv\) is part of a negative triangle in \(G^{\prime}\) exactly whenever  
\[\min_{u\in V}\{A_{vu}+B_{uz}\}<-D_{zv}.\]  
Assuming we can compute FindEdges for a \(k\)-node graph in \(T(n)\) rounds, with a non-positive matrix \(D=\mathbf{0}\) initialized, we can apply simultaneous binary searches on \(D_{zv}\), with values between \(\{-2M,0\}\), updating it for each node \(v\) after each run of FindEdges to find \(\min_{u\in V}\{A_{vu}+B_{uz}\}\) for every other node \(z\) in \(T(3n)\cdot\lceil\log(\max_{v,z\in V}\{\min_{u\in V}\{A_{vu}+B_{uv}\}\})\rceil\) rounds, since \(G^{\prime}\) is a tripartite graph with \(3n\) nodes.  
Remark 3: _This procedure can be realized in a single \(n\)-node distributed graph by letting each node represent the three copies of itself since \(G^{\prime}\) is tripartite. The \(T(3n)\) stems from each processor node possibly needing to send one message for each node it is simulating in each round of FindEdges. If the bandwidth per message is large enough (i.e., three times the bandwidth needed for solving FindEdges in \(T(n)\) rounds), then this can be conducted in \(T(n)\) rounds._  
Thus, for this binary search, each node \(v\) initializes and locally stores \(D_{vz}=0\) for each other \(z\in V\); subsequently, we solve FindEdges on \(G^{\prime}\). The node then updates each \(D_{vz}\) according to whether or not the edge copies of \(vz\) were part of a negative triangle in \(G^{\prime}\), after which, FindEdges is computed with the updated values for \(D\). This is repeated until all the \(\min_{u\in V}\{A_{vu}+B_{uz}\}\) are determined.