All pairs shortest paths with dynamic programming

Question

All,

I am reading about the relationship between all pairs shortest path and matrix multiplication.

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. 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.

It follows from this argument that A to power of n contains all shortest paths.

Question number 1:

My question is that in a graph we will be having at most n-1 edges between two nodes in a path, on what basis is the author discussing of path of length "n"?

Following slides

www.infosun.fim.uni-passau.de/br/lehrstuhl/.../Westerheide2.PPT

On slide 10 it is mentioned as below.

dij(1) = cij

dij(m) = min (dij(m-1), min1≤k≤n {dik(m-1) + ckj}) --> Eq 1
       = min1≤k≤n {dik(m-1) + ckj} ------------------> Eq 2

Question 2: how author concluded Eq 2 from Eq 1.

In Cormen et al book on introduction to algorithms, it is mentioned as below:

What are the actual shortest-path weights delta(i, j)? If the graph contains no negative-weight cycles, then all shortest paths are simple and thus contain at most n - 1 edges. A path from vertex i to vertex j with more than n - 1 edges cannot have less weight than a shortest path from i to j. The actual shortest-path weights are therefore given by

delta(i,j) = d(i,j) power (n-1) = (i,j) power (n) = (i,j) power (n+1) = ...

Question 3: in above equation how author came with n, n+1 edges as we have at most n-1, and also how above assignment works?

Thanks!

Answer 1

1. The n vs n-1 is just an unfortunate variable name choice. He should have used a different letter instead to be more clear.

   A^1 has the shortest paths of length up to 1 (trivially)
   A^2 has the shortest paths of length up to 2
   A^k has the shortest paths of length up to k
   

2. Eq 2 does not directly come from Eq1. Eq 2 is just the second term from the first equation. I presume this is a formatting or copy-paste error (I can't check - your ppt link is broken)

3. The author is just explicitly pointing out that you have nothing to gain by adding more then n-1 edges to the path:

   A^(n-1),            //the shortest paths of length up tp (n-1)
   is equal to A^n     //the shortest paths of length up tp (n)
   is equal to A^(n+1) //the shortest paths of length up tp (n+1)
   ...
   

   This is just so that you can safely stop your computations at (n-1) and be sure that you have the minimum paths among all paths of all lengths. (This is kind of obvious but the textbook has a point in being strict here...)

Answer 2

In a graph we will be having atmost n-1 edges between two nodes in a path, on what basis author is discussing of path of length "n"?

You're confusing the multiple measures being discussed:

• A^n represents the "shortest paths" (by weight) of length n between vertices.
• "at most n-1 edges between two nodes" -- I presume in this case you're thinking of n as the size of the graph.

The graph could have hundreds of vertices but your adjacency matrix A^3 shows the shortest paths of length 3. Different n measures.