<ol>
<li><p>The discussion in <a href="https://arxiv.org/pdf/cs/0008011.pdf" rel="nofollow noreferrer">this paper</a>, Section 3 beginning on page 7, might be useful to you.  It focuses on reducing distance product witnesses to distance product, which is the same as distance vs path APSP over the class of three-layered input graphs, but I believe the ideas in this paper and its references should also help in the fully general case.</p>
</li>
<li><p>This is not exactly the same as your question, but it follows from <a href="https://people.csail.mit.edu/virgi/tria-mmult-jv.pdf" rel="nofollow noreferrer">this classic paper</a> in fine-grained complexity that there is a subcubic algorithm for distance APSP iff there is a subcubic algorithm for path APSP.  For example, this paper proves that there is a subcubic algorithm that solves path APSP iff there is a subcubic algorithm that verifies a proposed solution to path APSP.  Verifying a solution to path APSP is trivial if we can efficiently compute the distance matrix.</p>
</li>
</ol>

CC BY-SA 4.0
2022-06-15T10:57:47.570Z
Hey thanks for the answer. I'm not really sure if I understand which equivalence you are referring to for the path verification result. Williams' paper doesn't explicitly define APSP or state a conjecture and for its results calls on the sub-cubic equivalence between the distance product and the distance version of APSP, which simply brings me back to my original confusion. In fact, this one of the papers I refer to when I say that some authors handle these differences very casually. It is a good point: if we have that path verification is equivalent to path computation, my problem is solved.
Koen
CC BY-SA 4.0
2022-06-11T14:43:59.700Z
2022-06-11T14:43:59.700Z
GMB
<p>I'm working on a project centered around the All-Pairs Shortest Paths (APSP) problem. Common algorithms to APSP (<a href="https://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm" rel="nofollow noreferrer">Floyd-Warshall</a>, <a href="https://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm" rel="nofollow noreferrer">Bellman-Ford</a>, <a href="https://en.wikipedia.org/wiki/Johnson%27s_algorithm" rel="nofollow noreferrer">Johnson's</a>) work with the standard definition of the problem where we are tasked to output the shortest <em>paths</em> between all nodes in a given directed input graph. We work in the adjacency model for graphs and assume an APSP instance is represented by its weight matrix <span class="math-container">$W$</span> s.t. if <span class="math-container">$w$</span> is the weight function for our input graph <span class="math-container">$G=(V,E)$</span>, we have that <span class="math-container">$W[ij]=w(i,j)$</span> if there is an edge <span class="math-container">$(i,j)$</span> and <span class="math-container">$W[ij]=\infty$</span> otherwise. For a graph over <span class="math-container">$n$</span> nodes we can solve APSP by outputting <span class="math-container">$n$</span> shortest path trees or by outputting a successor matrix. A shortest path tree <span class="math-container">$T$</span> is a rooted tree and sub-graph of <span class="math-container">$G$</span> such that the paths from the root of <span class="math-container">$T$</span> to any other nodes in <span class="math-container">$V$</span> are exactly the shortest paths in <span class="math-container">$G$</span>. A successor matrix <span class="math-container">$S$</span> is defined s.t. <span class="math-container">$S[ij]=k$</span> iff <span class="math-container">$k$</span> is the next node on the shortest path from <span class="math-container">$i$</span> to <span class="math-container">$j$</span>.</p>
<p>In the field of fine-grained complexity where I'm doing my project it is common to work with a version of the problem where we are only tasked to output the shortest <em>distances</em> between all nodes in a graph, see e.g., <a href="https://people.csail.mit.edu/virgi/eccentri.pdf" rel="nofollow noreferrer">this excellent overview</a>. This way we can solve APSP by repeated use of the <a href="https://en.wikipedia.org/wiki/Min-plus_matrix_multiplication" rel="nofollow noreferrer">distance product</a> of the weight matrix. We output these distances as a distance matrix <span class="math-container">$D$</span> s.t. <span class="math-container">$D[ij]$</span> is the length of the shortest path from <span class="math-container">$i$</span> to <span class="math-container">$j$</span> in <span class="math-container">$G$</span>.</p>
<p>We work under the conjecture that no <span class="math-container">$O(n^{3-\epsilon})$</span> time algorithm exists, for <span class="math-container">$\epsilon&gt;0$</span>, for APSP and this conjecture seems reasonable for both versions of the problem.</p>
<p>My problem is that I can't find a good source that dives deep into the distinction between these two versions of the problem and most of the works I've read seem to work with their preferred version of the problem without explaining why it is fine to just work with e.g. the distance version of APSP.</p>
<p>The paths version of the problem seems harder than the distance version of the problem; most algorithms for computing the paths between all nodes already keep track of all shorstest distances during their run. Computing the distance matrix from the successor matrix in sub-cubic, i.e. <span class="math-container">$O(n^{3-\epsilon})$</span>, time should not be too hard. The other direction is not obvious to me at all.</p>
<p>From the facts that the problems have the same common hardness conjecture, and how casually some authors handle the differences, I feel like these two problems should be sub-cubic equivalent: a <span class="math-container">$O(n^{3-\epsilon})$</span> time algorithm for one should imply a <span class="math-container">$O(n^{3-\epsilon})$</span> time algorithm for the other.</p>
<p>My questions:</p>
<ol>
<li><p>Does anyone know of a good discussion they could point me to that clarifies the relationship between these two versions of the problem?</p>
</li>
<li><p>Is there a sub-cubic time algorithm that solves the paths version of APSP on the condition that we are provided with the distance matrix as input?</p>
</li>
</ol>

CC BY-SA 4.0
2022-06-03T05:38:09.227Z
Is this for directed or undirected graphs?
daniello
CC BY-SA 4.0
2022-06-15T10:35:51.310Z
This is for directed graphs, I've edited.
Koen
<graph-algorithms><time-complexity><shortest-path><fine-grained>
Solving All-Pairs Shortest Paths using a distance matrix in sub-cubic time
Koen
# Solving All-Pairs Shortest Paths using a distance matrix in sub-cubic time

(Asked by: username_0 on 2022-06-01)

I'm working on a project centered around the All-Pairs Shortest Paths (APSP) problem. Common algorithms to APSP ([Floyd-Warshall](https://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm), [Bellman-Ford](https://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm), [Johnson's](https://en.wikipedia.org/wiki/Johnson%27s_algorithm)) work with the standard definition of the problem where we are tasked to output the shortest *paths* between all nodes in a given directed input graph. We work in the adjacency model for graphs and assume an APSP instance is represented by its weight matrix $W$ s.t. if $w$ is the weight function for our input graph $G=(V,E)$, we have that $W[ij]=w(i,j)$ if there is an edge $(i,j)$ and $W[ij]=\infty$ otherwise. For a graph over $n$ nodes we can solve APSP by outputting $n$ shortest path trees or by outputting a successor matrix. A shortest path tree $T$ is a rooted tree and sub-graph of $G$ such that the paths from the root of $T$ to any other nodes in $V$ are exactly the shortest paths in $G$. A successor matrix $S$ is defined s.t. $S[ij]=k$ iff $k$ is the next node on the shortest path from $i$ to $j$.

In the field of fine-grained complexity where I'm doing my project it is common to work with a version of the problem where we are only tasked to output the shortest *distances* between all nodes in a graph, see e.g., [this excellent overview](https://people.csail.mit.edu/virgi/eccentri.pdf). This way we can solve APSP by repeated use of the [distance product](https://en.wikipedia.org/wiki/Min-plus_matrix_multiplication) of the weight matrix. We output these distances as a distance matrix $D$ s.t. $D[ij]$ is the length of the shortest path from $i$ to $j$ in $G$.

We work under the conjecture that no $O(n^{3-\epsilon})$ time algorithm exists, for $\epsilon>0$, for APSP and this conjecture seems reasonable for both versions of the problem.

My problem is that I can't find a good source that dives deep into the distinction between these two versions of the problem and most of the works I've read seem to work with their preferred version of the problem without explaining why it is fine to just work with e.g. the distance version of APSP.

The paths version of the problem seems harder than the distance version of the problem; most algorithms for computing the paths between all nodes already keep track of all shorstest distances during their run. Computing the distance matrix from the successor matrix in sub-cubic, i.e. $O(n^{3-\epsilon})$, time should not be too hard. The other direction is not obvious to me at all.

From the facts that the problems have the same common hardness conjecture, and how casually some authors handle the differences, I feel like these two problems should be sub-cubic equivalent: a $O(n^{3-\epsilon})$ time algorithm for one should imply a $O(n^{3-\epsilon})$ time algorithm for the other.

My questions:

1. Does anyone know of a good discussion they could point me to that clarifies the relationship between these two versions of the problem?
2. Is there a sub-cubic time algorithm that solves the paths version of APSP on the condition that we are provided with the distance matrix as input?

**Tags:** graph-algorithms, time-complexity, shortest-path, fine-grained
> **Comments:**
> **username_1**: Is this for directed or undirected graphs?  
> **username_0**: This is for directed graphs, I've edited.  

---

## 1 answers

### Answer by username_2 on 2022-06-11. Score: 3

1. The discussion in [this paper](https://arxiv.org/pdf/cs/0008011.pdf), Section 3 beginning on page 7, might be useful to you. It focuses on reducing distance product witnesses to distance product, which is the same as distance vs path APSP over the class of three-layered input graphs, but I believe the ideas in this paper and its references should also help in the fully general case.
2. This is not exactly the same as your question, but it follows from [this classic paper](https://people.csail.mit.edu/virgi/tria-mmult-jv.pdf) in fine-grained complexity that there is a subcubic algorithm for distance APSP iff there is a subcubic algorithm for path APSP. For example, this paper proves that there is a subcubic algorithm that solves path APSP iff there is a subcubic algorithm that verifies a proposed solution to path APSP. Verifying a solution to path APSP is trivial if we can efficiently compute the distance matrix.

> **Comments:**
> **username_0**: Hey thanks for the answer. I'm not really sure if I understand which equivalence you are referring to for the path verification result. Williams' paper doesn't explicitly define APSP or state a conjecture and for its results calls on the sub-cubic equivalence between the distance product and the distance version of APSP, which simply brings me back to my original confusion. In fact, this one of the papers I refer to when I say that some authors handle these differences very casually. It is a good point: if we have that path verification is equivalent to path computation, my problem is solved.  

---

