4

In the lecture we are taught that we can solve All Pairs Shortest Path(APSP) with matrix multiplication.

In APSP we are creating a distance table for all the distances between each nodes in the graph. And now the question is "Is it possible to solve Single Source Shortest Path(SSSP) problem with matrix multiplication? If it is, then how?"

If you give me an explanation how to accomplish this I would appreciate.

Improve this question
7
  • 1
    I took the freedom to remove the request for third party resources to avoid a quick close.
    – Doc Brown
    Dec 25, 2015 at 9:13
  • If that was your question, you should have written it using that words. Hope I got your intention right.
    – Doc Brown
    Dec 25, 2015 at 9:15
  • 1
    I will not answer your homework question directly, but I will give you the observation that the APSP can be calculated by calculating the SSSP N times, using each node as a source.
    – Bart van Ingen Schenau
    Dec 25, 2015 at 9:32
  • 3
    @mrgenco: the more interesting question would be if you can solve sssp with matrix multiplication without calculating shortest paths for other nodes with better runtime order than the algorithm you learned for APSP. If that is what you want to know, you should ask precisely that.
    – Doc Brown
    Dec 25, 2015 at 10:02
  • 1
    Take also a look here for a dynamic programming solution
    – Marco A.
    Dec 30, 2015 at 6:12

1 Answer 1

Reset to default
4

Single Source Shortest Path?

Since all pair shortest path is possible with Matrix Multiplication and single source is a subset for all pair source, Single source shortest path is also possible. Just ignore the other pairs.

Matrix-Multiplication Based Algorithm

  1. Consider the multiplication of the weighted adjacency matrix with itself - except, in this case, we replace the multiplication operation in matrix multiplication by addition, and the addition operation by minimization
  2. Notice that the product of weighted adjacency matrix with itself returns a matrix that contains shortest paths of length 2 between any pair of nodes
  3. It follows from this argument that An contains all shortest paths
  4. An is computed by doubling powers - i.e., as A, A2, A4, A8, ...
  5. We need log(n) matrix multiplications, each taking time O(n3)
  6. The serial complexity of this procedure is O(n3 log (n))
  7. This algorithm is not optimal, since the best known algorithms have complexity O(n3)

graph and assorted matrixes

Improve this answer
0

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.