## 4 APSP and Routing Tables
### Routing Tables via Efficient Computation of Witness Matrices  
For the routing table entries, we also need each node \(v\) to know the intermediate node \(u\) that is being used to attain \(\min_{u\in V}\{W_{vu}+W_{uz}\}\).  
Definition 7: For a distance product \(A\star B\) of two \(n\times n\) matrices \(A,B,a\) witness matrix \(C\) is an \(n\times n\) matrix, such that  
\[C_{ij}\in argmin_{k\in[n]}\{A_{ik}+B_{kj}\}\]  
To put it simply, a witness matrix contains the intermediate entries used to attain the values in the resulting distance product. We present here a simple way of computing witness matrices along with the distance product by modifying the matrix entries appropriately, first considered by [17]. The approach is well-suited for our algorithm, as we only incur \(\mathcal{O}(\log n)\) additional calls to FindEdges for a distance product computation with a witness matrix.  
For an \(n\times n\) integer matrix \(W\), obtain matrices \(W^{\prime}\) and \(W^{\prime\prime}\) by taking \(W^{\prime}_{ij}=nW_{ij}+j-1\) and \(W^{\prime\prime}_{ji}=nW_{ji}\). Set \(K=W^{\prime}\star W^{\prime\prime}\).  
**Claim 1**.: _With \(W,W^{\prime},W^{\prime\prime}\), and \(K\) as defined immediately above,_  
1. \(\left\lfloor\frac{K}{n}\right\rfloor=W^{2,\star}\)__
2. \((K\mod n)+1\) _is a witness matrix for_ \(W^{2,\star}\)_._  
The claim follows from routine calculations of the quantities involved and can be found in Appendix A.1.  
Hence, we can obtain witness matrices by simply changing the entries of our matrices by no more than a multiplicative factor of \(n\) and an addition of \(n\). Since the complexity of our method logarithmically depends on the magnitude of the entries of \(W\), we only logarithmically need many more calls to FindEdges to obtain witness matrices along with the distance products, making this simple method well-suited for our approach. More precisely, we can compute \(W^{2}\) with a witness matrix using \(\left\lceil\log\left(2n\cdot\max_{i,j}\{W_{ij}^{2}<\infty\}\right)\right\rceil\), calls to FindEdges. We obtain the following corollary to Proposition 1 to characterize the exact number of rounds needed:  
**Corollary 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 square \(W^{2,\star}\), along with a witness matrix \(H\), can be computed in \(T(3n)\cdot\lceil\log_{2}(n\cdot\max_{v,z\in G}\{\min_{u\in V}\{W_{vu}+W_{uv}\} \}+n)\rceil\) rounds._  
Proof.: This follows from Claim 1 and Proposition 1 upon observing that  
\(\max_{v\in V}\{\min_{u\in V}\{W^{\prime}_{vu}+W^{\prime\prime}_{uv}\}\}\}\leq n \cdot\max_{v,z\in G}\{\min_{u\in V}\{W_{vu}+W_{uv}\}\}+n\).  
Once we obtain witness matrices along with the distance product computations, constructing the routing tables for each node along the way of computing APSP is straightforward. In each squaring of \(W\) in Equation (2), each node updates its routing table entries according to the corresponding witness matrix entry observed. It is worth noting that these routing table entries only need to be stored and accessed classically so that we avoid using unnecessary quantum data storage.