4
$\begingroup$

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.

$\endgroup$
  • 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$ – Sasho Nikolov Oct 20 '12 at 1:13
  • $\begingroup$ @SashoNikolov thanks, this is a sufficient answer to my question. $\endgroup$ – Immanuel Weihnachten Oct 20 '12 at 1:40
  • 1
    $\begingroup$ @SashoNikolov maybe convert to an answer ? $\endgroup$ – Suresh Venkat Oct 20 '12 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 '12 at 3:37
  • $\begingroup$ 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. $\endgroup$ – Immanuel Weihnachten Oct 20 '12 at 19:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.