## A Visual Guide to Floyd-Warshall and Matrix Multiplication

The goal of the Floyd-Warshall algorithm is to find the shortest paths in a tree using Dynamic Programming. Let’s get started with an example.

The Floyd-Warshall algorithm starts by gathering the initial weights and placing them into a matrix. Since there are 4 vertices, the matrix will have 4 rows and 4 columns.

Starting with vertex 1, the algorithm gathers the initial weights from 1 to the other 3 vertices. It will place a 0 for itself and infinity if there is no direct path. The edge weight from 1 to itself is 0. The edge weight from 1 to 2 is 10. Since there is no direct path from 1 to 3 the algorithm places infinity as the placeholder. The edge weight from 1 to 4 is 5.

The first row is complete and the Floyd-Warshall algorithm will work on vertex 2 next, which corresponds to the second row. There is no direct path from 2 to 1, so infinity is placed. The weight from 2 to itself is 0. There is no direct path from 2 to 3, so infinity is placed. Lastly, the edge weight from 2 to 4 is 9.

The Floyd-Warshall algorithm will work on vertex 3 next which corresponds to the third row. The edge weight from 3 to 1 is -2. The edge weight from 3 to 2 is 4. The edge weight from 3 to itself is 0. Finally, the edge weight from 3 to 4 is infinity since there is no direct path from 3 to 4.

The final row corresponds to the last vertex, which is vertex 4. A similar principle is applied. The weight from 4 to 1 is infinity since there is no direct path from 4 to 1. The edge weight from 4 to 2 is -3. The edge weight from 4 to 3 is 1 and the weight from 4 to itself is 0.

Now that the initial matrix, D*0*, is created, the Floyd-Warshall algorithm will generate matrices D*1* through D*4*. Although exhaustive, my goal is to provide you with each step of this process. To generate D*1*, the algorithm will use D*0* and see if there is a shorter approach from 2 to 3, for example, by going from 2 to 1 and then from 1 to 3. Since the algorithm is building D*1*, the first row and the first column are locked and cannot be modified. Looking at the diagonal, they are all 0’s, so the diagonal will not change since there are no self-loops present in the provided graph. Before starting, D*1* will look like the following matrix.

The blank fields in the matrix are the ones that the Floyd-Warshall algorithm will focus on.

To get the value for D*1* row 2, column 3, the following operations are performed:

- The value for (2,3) is retrieved from D
*0* - The value D
*0*(2,3) is compared with the sum of the values D*0*(2,1) + D*0*(1,3).**Vertex 1 is the intermediate vertex for this graph**meaning that you will always go through 1 in order to generate D1.

- D
*0*(2,3) = D*0*(2,1) + D*0*(1,3): ∞ = ∞ + ∞ - Infinity is kept in place for D
*1*(2,3)

Next, the algorithm will focus on D*1*(2,4)

Since D*0*(2,4) is less than D*0*(2,1) + D*0*(1,4), the value of 9 is placed into D*0*(2,4).

Next, the algorithm will focus on D*1*(3,2).

Since D*0*(3,2) is less than D*0*(3,1) + D*0*(1,2), 4 is preserved for D*1*(3,2).

Next, the algorithm focuses on D*1*(3,4).

Since D*0*(3,4) > D*0*(3,1) + D*0*(1,4), field D*1*(3,4) is updated with 3.

Next, the algorithm focuses on D*1*(4,2).

Since D*0*(4,2) < D*0*(4,1) + D*0*(1,2), -3 is preserved for D*1*(4,2).

Finally, the Floyd-Warshall algorithm looks at D*1*(4,3).

Since D*0*(4,3) < D*0*(4,1) + D*0*(1,3), 1 is preserved for D*1*(4,3).

After all those steps, D*1* is finally complete. Next, the Floyd-Warshall algorithm will create D*2*, D*3*, and D*4*. To create D*2*, the algorithm takes the D*1* matrix as the starting point and fills in the data that is guaranteed not to change. The fields that are guaranteed not to change in this step are the diagonals, the second row, and the second column values.

The Floyd-Warshall algorithm starts by examining D*2*(1,3) by **going through 2**.

Since D*1*(1,3) = D*1*(1,2) + D*1*(2,3), ∞ is preserved for D*1*(1,3).

Next, the algorithm focuses on D*2*(1,4).

Since D*1*(1,4) < D*1*(1,2) + D*1*(2,4), 5 is preserved.

Next, the algorithm focuses on D2(3,1).

Since D*1*(3,1) < D*1*(3,2) + D*1*(2,1), -2 is preserved.

Next, the algorithm focuses on D*2*(3,4).

Since D*1*(3,4) < D*1*(3,2) + D*1*(2,4), 3 is preserved for D*2*(3,4).

Next, the Floyd-Warshall algorithm focuses on D*2*(4,1) by going through vertex 2.

Since D*1*(4,1) = D*1*(4,2) + D*1*(2,1), there is no change from D*1* to D*2*.

Finally, the algorithm examines D*2*(4,3).

Since D*1*(4,3) < D*1*(4,2) + D*1*(2,3), 1 is preserved.

The Floyd-Warshall algorithm completes the D*2* matrix; D*3* is next. To create D*3*, the algorithm takes the D*2* matrix as the starting point and fills in the data that is guaranteed not to change. The fields that are guaranteed not to change in this step are the diagonals, the third row, and the third column values.

The Floyd-Warshall algorithm starts by examining D*3*(1,2) by **going through vertex 3**.

Since D*2*(1,2) < D*2*(1,3) + D*2*(3,1), 10 is preserved.

Next, the algorithm focuses on D*3*(1,4).

Since D*2*(1,4) < D*2*(1,3) + D*2*(3,4), 5 is preserved.

Next, the algorithm focuses on D*3*(2,1).

Since D*2*(2,1) = D*2*(2,3) + D*2*(3,1), there is no change.

Next, the algorithm focuses on D*3*(2,4).

Since D*2*(2,4) < D*2*(2,3) + D*2*(3,4), 9 is preserved.

Next, the algorithm focuses on D*3*(4,1).

Since D*2*(4,1) > D*2*(4,3) + D*2*(3,1), D*3*(4,1) is updated to -1.

Finally, the algorithm examines D*3*(4,2).

Since D*2*(4,2) < D*2*(4,3) + D*2*(3,2), -3 is preserved and the algorithm finishes the construction of the D*3* matrix.

The Floyd-Warshall algorithm has finally made it to D*4*. To construct D*4*, the algorithm takes the D*3* matrix as the starting point and fills in the data that is guaranteed not to change. The fields that are guaranteed not to change in this step are the diagonals, the fourth row, and the fourth column values.

The Floyd-Warshall algorithm starts by examining D*4*(1,2) **by going through vertex 4**.

Since D*3*(1,2) > D*3*(1,4) + D*3*(4,2), D*4*(1,2) is updated to the new value of 2.

Next, the algorithm focuses on D*4*(1,3).

Since D*3*(1,3) > D*3*(1,4) + D*3*(4,3), D*4*(1,3) is updated to the new value of 6.

Next, the algorithm focuses on D*4*(2,1).

Since D*3*(2,1) > D*3*(2,4) + D*3*(4,1), D*4*(2,1) is updated to the new value of 8.

Next, the algorithm focuses on D*4*(2,3).

Since D*3*(2,3) > D*3*(2,4) + D*3*(4,3), D*4*(2,3) is updated to the new value of 10.

Next, the algorithm focuses on D*4*(3,1).

Since D*3*(3,1) < D*3*(3,4) + D*3*(4,1), -2 is preserved.

Finally, the Floyd-Warshall algorithm focuses on D*4*(3,2).

Since D*3*(3,2) > D*3*(3,4) + D*3*(4,2), D*4*(3,2) is updated to the new value of 0, and the algorithm is complete.

Looking over the entire process, the Floyd-Warshall algorithm produces the following matrices:

If you examine the values of matrix D*4* by comparing it to the tree, you’ll see that the shortest path is found from each vertex to each vertex. Some vertices can be reached by one hop, others by two, and some even by three.