<p>I didn't find deep informations on <a href="http://en.wikipedia.org/wiki/Shortest_path_problem#All-pairs_shortest_paths" rel="nofollow">Wikipedia about all-pairs shortest path</a>, in particular I do not know what is the best algorithm to solve this problem beyond Floyd-Warshall's one, then I do not know if the following observation is too irrelevant or trivial. </p>

<p>In <a href="http://en.wikipedia.org/wiki/Max-plus_algebra" rel="nofollow">maxplus algebra</a> we revisited linear algebra substituting the usual operations with the max-operation and plus-operation instead of addition and multiplication respectively. In particular we obtain an equivalent theory by taking minimum instead of maximum, then having a minplus algebra (with the obvious changing in the associated semiring, i.e. taking $+\infty$ instead of $-\infty$ as neutral element for the first operation).</p>

<p>Trying to see what the usual graph-theoretic-interpretation of matrix multiplication become in the minplus algebra (with $+\infty$ in the entries corresponding to non-existing edge and $0$s on the diagonal), I see that the $k$-th power of the adjacency matrix gives the shortest paths of length at most $k$. Then, all-pairs shortest path could be solved in $n^\omega \log n$ (where $\omega$ is the present lowest exponent for matrix multiplication) instead of $n^3$ like FW-alg. </p>

<p>Did I made big mistakes about all that? </p>

<p>I consider that maybe the lower bounds on matrix multiplication are not valid changing operations... but then seems plausible that it could be possible to have an exponent less than $3$ also for minplus algebraic matrix multiplication; among other things, the multiplication is far more computationally expensive than addition, and so is taking minimum respect to addition.</p>

CC BY-SA 3.0
2012-10-25T05:01:24.883Z
Yes, a "truly subcubic", i.e. $O(n^{3-\varepsilon})$ time algorithm for APSP is a big open problem in graph algorithms (one of my favorite). There are many problems that are equivalent to APSP in the sense that truly subcubic time algorithms for them imply one for APSP and vice versa (e.g. second shortest path, min weight triangle,...). Also, the slightly subcubic algorithm by Chan was recently improved, ever so slightly, by Yijie Han and Tadao Takaoka in SWAT'12. The current best runtime is now $O(n^3 \log\log n / \log^2 n)$.
virgi
CC BY-SA 3.0
2012-10-20T01:13:55.057Z
the computational cost of multiplication of numbers does  not matter much -- it's a cheap operation in this context. if you take a look at say Strassen's algorithm you'll realize that you need an additive inverse to make it work, but min is not invertible. APSP is actually just as expensive as min-plus matrix product (MPP), but we don't know how to do MPP faster than $O(n^3)$ either. However, there are matrix multiplication-based algorithms for special cases of APSP, see [this](http://www.diku.dk/PATH05/Uri1.pdf) and [this](http://www.mimuw.edu.pl/~mucha/teaching/alp2006/seidel92.pdf)
Sasho Nikolov
CC BY-SA 3.0
2012-10-20T01:40:01.897Z
@SashoNikolov thanks, this is a sufficient answer to my question.
Immanuel Weihnachten
CC BY-SA 3.0
2012-10-20T03:25:55.043Z
@SashoNikolov maybe convert to an answer ?
Suresh Venkat
CC BY-SA 3.0
2012-10-20T03:37:52.170Z
_we don't know how to do MPP faster than $O(n^3)$ either_ — Actually, yes, we do!  See [these papers by Timothy Chan](https://cs.uwaterloo.ca/~tmchan/pub_apsp.html).  (Admittedly, only polylog n faster, but still.)
Jeffε
CC BY-SA 3.0
2012-10-20T19:46:48.627Z
Very interesting. The Wikipedia article on APSP should be edited to include the fastest algorithm to solve it in general, that according to what is said here is to use the one by Timothy Chan.
Immanuel Weihnachten
CC BY-SA 3.0
2012-10-21T02:24:13.263Z
@JɛﬀE good point, I admit I did not know that paper. I don't feel familiar enough with APSP literature, my knowledge is mostly at the graduate algorithms level. Maybe someone more familiar can answer this one? But $n^{3-\epsilon}$ for $\epsilon > 0$ constant must still be wide open
Sasho Nikolov
<ds.algorithms><graph-algorithms><linear-algebra><shortest-path><matrix-product>
What about apply maxplus algebra for all-pairs shortest paths?
Immanuel Weihnachten
# What about apply maxplus algebra for all-pairs shortest paths?

(Asked by: username_0 on 2012-10-19)

I didn't find deep informations on [Wikipedia about all-pairs shortest path](http://en.wikipedia.org/wiki/Shortest_path_problem#All-pairs_shortest_paths), in particular I do not know what is the best algorithm to solve this problem beyond Floyd-Warshall's one, then I do not know if the following observation is too irrelevant or trivial.

In [maxplus algebra](http://en.wikipedia.org/wiki/Max-plus_algebra) we revisited linear algebra substituting the usual operations with the max-operation and plus-operation instead of addition and multiplication respectively. In particular we obtain an equivalent theory by taking minimum instead of maximum, then having a minplus algebra (with the obvious changing in the associated semiring, i.e. taking $+\infty$ instead of $-\infty$ as neutral element for the first operation).

Trying to see what the usual graph-theoretic-interpretation of matrix multiplication become in the minplus algebra (with $+\infty$ in the entries corresponding to non-existing edge and $0$s on the diagonal), I see that the $k$-th power of the adjacency matrix gives the shortest paths of length at most $k$. Then, all-pairs shortest path could be solved in $n^\omega \log n$ (where $\omega$ is the present lowest exponent for matrix multiplication) instead of $n^3$ like FW-alg.

Did I made big mistakes about all that?

I consider that maybe the lower bounds on matrix multiplication are not valid changing operations... but then seems plausible that it could be possible to have an exponent less than $3$ also for minplus algebraic matrix multiplication; among other things, the multiplication is far more computationally expensive than addition, and so is taking minimum respect to addition.

**Tags:** ds.algorithms, graph-algorithms, linear-algebra, shortest-path, matrix-product
> **Comments:**
> **username_2**: the computational cost of multiplication of numbers does  not matter much -- it's a cheap operation in this context. if you take a look at say Strassen's algorithm you'll realize that you need an additive inverse to make it work, but min is not invertible. APSP is actually just as expensive as min-plus matrix product (MPP), but we don't know how to do MPP faster than $O(n^3)$ either. However, there are matrix multiplication-based algorithms for special cases of APSP, see [this](http://www.diku.dk/PATH05/Uri1.pdf) and [this](http://www.mimuw.edu.pl/~mucha/teaching/alp2006/seidel92.pdf)  
> **username_0**: @SashoNikolov thanks, this is a sufficient answer to my question.  
> **username_3**: @SashoNikolov maybe convert to an answer ?  
> **username_4**: _we don't know how to do MPP faster than $O(n^3)$ either_ — Actually, yes, we do!  See [these papers by Timothy Chan](https://cs.uwaterloo.ca/~tmchan/pub_apsp.html).  (Admittedly, only polylog n faster, but still.)  
> **username_0**: Very interesting. The Wikipedia article on APSP should be edited to include the fastest algorithm to solve it in general, that according to what is said here is to use the one by Timothy Chan.  
> **username_2**: @JɛﬀE good point, I admit I did not know that paper. I don't feel familiar enough with APSP literature, my knowledge is mostly at the graduate algorithms level. Maybe someone more familiar can answer this one? But $n^{3-\epsilon}$ for $\epsilon > 0$ constant must still be wide open  
> **username_1**: Yes, a "truly subcubic", i.e. $O(n^{3-\varepsilon})$ time algorithm for APSP is a big open problem in graph algorithms (one of my favorite). There are many problems that are equivalent to APSP in the sense that truly subcubic time algorithms for them imply one for APSP and vice versa (e.g. second shortest path, min weight triangle,...). Also, the slightly subcubic algorithm by Chan was recently improved, ever so slightly, by Yijie Han and Tadao Takaoka in SWAT'12. The current best runtime is now $O(n^3 \log\log n / \log^2 n)$.  

---

## 0 answers

