I didn't find deep informations on Wikipedia about all-pairs shortest path, 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 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.

  • 8
    $\begingroup$ 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 and this $\endgroup$ Oct 20, 2012 at 1:13
  • $\begingroup$ @SashoNikolov thanks, this is a sufficient answer to my question. $\endgroup$ Oct 20, 2012 at 1:40
  • 1
    $\begingroup$ @SashoNikolov maybe convert to an answer ? $\endgroup$ Oct 20, 2012 at 3:25
  • 6
    $\begingroup$ we don't know how to do MPP faster than $O(n^3)$ either — Actually, yes, we do! See these papers by Timothy Chan. (Admittedly, only polylog n faster, but still.) $\endgroup$
    – Jeffε
    Oct 20, 2012 at 3:37
  • 1
    $\begingroup$ 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)$. $\endgroup$
    – virgi
    Oct 25, 2012 at 5:01


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.