## All-Pairs Shortest Path Matrix Multiplication

You’re presented with a graph and your goal is to find all-pairs of shortest paths using dynamic programming.

The first step is to create a matrix where the number of rows and columns equals the number of vertices and then to populate it with initial data. For each vertex that can be reached by one hop, you will populate it with the edge weight. If a vertex cannot be reached with one hop, you will populate it with infinity and if a vertex is trying to reach itself, you will populate it with zero. Let’s walk through the algorithm to populate the initial matrix.

We’ll start by populating all the zeros. The zeros will be down the diagonal. Why? Looking at the first entry at A*1*(1,1), you’re trying to go from vertex 1 to vertex 1. What’s the weight of that? Zero. Same occurs for (2,2), (3,3), and (4,4).

Let’s examine A*1*(1,2) next. You can get from vertex 1 to 2 in one hop. The edge weight is 10.

Next, we’ll look at A*1*(1,3). Since you cannot get to vertex 3 from vertex 1 in one hop, you enter infinity.

Let’s fill in the rest of the fields.

- From 1 to 4, A
*0*(1,4) = 5 - From 2 to 1, A
*0*(2,1) = ∞ - From 2 to 3, A
*0*(2,3) = ∞ - From 2 to 4, A
*0*(2,4) = 9 - From 3 to 1, A
*0*(3,1) = -2 - From 3 to 2, A
*0*(3,2) = 4 - From 3 to 4, A
*0*(3,4) = ∞ - From 4 to 1, A
*0*(4,1) = ∞ - From 4 to 2, A
*0*(4,2) = -3 - From 4 to 3, A
*0*(4,3) = 1

Next, let’s look at the algorithm programmatically and visually.

We start with trying to obtain the value for A*0*(1,1). If we follow the for loop, k will be equal to 1, then 2, then 3 and finally 4 while the values of i and j do not change.

Next, plug in the values for those entries.

The minimum value is 0. So, we take the value of zero and plug it into A*1*(1,1)

Next, we’ll examine A1(1,2), but this time we’ll do it visually. What we did in the previous example is go through the row and the column corresponding to the entry. Since we looked at entry (1,1), we added the values from the first row and the first column and then got the minimum of those entries. Let’s start off by highlighting the first row and second column since we’re working on entry (1,2).

If we walk through the algorithm we add (1,1) to (1,2), (1,2) to (2,2), (1,3) to (3,2) and (1,4) to (4,2).

The minimum is 2 so we update A*2*(1,2) with 2.

Let’s fill out the rest of the cells visually as well for the first row. A2(1,3) is next.

The minimum is 6 so we update A*2*(1,3) with 6. A*2*(1,4) is next.

The minimum is 5 so we update A*2*(1,4) with 5. A*2*(2,1) is next.

The value is still infinity, so we update A*2*(2,1) with ∞. A*2*(2,2) is next.

For the remainder of the iteration in constructing A*2*, I’ll list the items and you can verify them by following through the matrix A*1*.

The final product looks like the following:

We keep repeating the procedure until we’re able to observe one of two occurrences:

- The entries from the previous matrix to the current matrix don’t change
- There is a negative value in the diagonal. This indicates a negative cycle and the values will decrease indefinitely.

What exactly is the A*2* matrix? It’s the result of modified matrix multiplication of two A*1* matrices. The next matrix to find is A*4*. That will be accomplished by multiplying two A*2* matrices. Let’s run through the entire process.

Since the matrix changed from the previous version, we’re still not finished. Time to move to A*8*.

Since there are no changes between A4 and A8, no further action is necessary.

*If you liked what you read, check out my book, **An Illustrative Introduction to Algorithms**.*