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 A1(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 A1(1,2) next. You can get from vertex 1 to 2 in one hop. The edge weight is 10.
Next, we’ll look at A1(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, A0(1,4) = 5
- From 2 to 1, A0(2,1) = ∞
- From 2 to 3, A0(2,3) = ∞
- From 2 to 4, A0(2,4) = 9
- From 3 to 1, A0(3,1) = -2
- From 3 to 2, A0(3,2) = 4
- From 3 to 4, A0(3,4) = ∞
- From 4 to 1, A0(4,1) = ∞
- From 4 to 2, A0(4,2) = -3
- From 4 to 3, A0(4,3) = 1
Next, let’s look at the algorithm programmatically and visually.
We start with trying to obtain the value for A0(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 A1(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 A2(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 A2(1,3) with 6. A2(1,4) is next.
The minimum is 5 so we update A2(1,4) with 5. A2(2,1) is next.
The value is still infinity, so we update A2(2,1) with ∞. A2(2,2) is next.
For the remainder of the iteration in constructing A2, I’ll list the items and you can verify them by following through the matrix A1.
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 A2 matrix? It’s the result of modified matrix multiplication of two A1 matrices. The next matrix to find is A4. That will be accomplished by multiplying two A2 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 A8.
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.