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, D0, is created, the Floyd-Warshall algorithm will generate matrices D1 through D4. Although exhaustive, my goal is to provide you with each step of this process. To generate D1, the algorithm will use D0 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 D1, 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, D1 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 D1 row 2, column 3, the following operations are performed:

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

• D0(2,3) = D0(2,1) + D0(1,3): ∞ = ∞ + ∞
• Infinity is kept in place for D1(2,3)

Next, the algorithm will focus on D1(2,4)

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

Next, the algorithm will focus on D1(3,2).

Since D0(3,2) is less than D0(3,1) + D0(1,2), 4 is preserved for D1(3,2).

Next, the algorithm focuses on D1(3,4).

Since D0(3,4) > D0(3,1) + D0(1,4), field D1(3,4) is updated with 3.

Next, the algorithm focuses on D1(4,2).

Since D0(4,2) < D0(4,1) + D0(1,2), -3 is preserved for D1(4,2).

Finally, the Floyd-Warshall algorithm looks at D1(4,3).

Since D0(4,3) < D0(4,1) + D0(1,3), 1 is preserved for D1(4,3).

After all those steps, D1 is finally complete. Next, the Floyd-Warshall algorithm will create D2, D3, and D4. To create D2, the algorithm takes the D1 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 D2(1,3) by going through 2.

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

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

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

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

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

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

Since D1(3,4) < D1(3,2) + D1(2,4), 3 is preserved for D2(3,4).

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

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

Finally, the algorithm examines D2(4,3).

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

The Floyd-Warshall algorithm completes the D2 matrix; D3 is next. To create D3, the algorithm takes the D2 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 D3(1,2) by going through vertex 3.

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

Next, the algorithm focuses on D3(1,4).

Since D2(1,4) < D2(1,3) + D2(3,4), 5 is preserved.

Next, the algorithm focuses on D3(2,1).

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

Next, the algorithm focuses on D3(2,4).

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

Next, the algorithm focuses on D3(4,1).

Since D2(4,1) > D2(4,3) + D2(3,1), D3(4,1) is updated to -1.

Finally, the algorithm examines D3(4,2).

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

The Floyd-Warshall algorithm has finally made it to D4. To construct D4, the algorithm takes the D3 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 D4(1,2) by going through vertex 4.

Since D3(1,2) > D3(1,4) + D3(4,2), D4(1,2) is updated to the new value of 2.

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

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

Next, the algorithm focuses on D4(2,1).

Since D3(2,1) > D3(2,4) + D3(4,1), D4(2,1) is updated to the new value of 8.

Next, the algorithm focuses on D4(2,3).

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

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

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

Finally, the Floyd-Warshall algorithm focuses on D4(3,2).

Since D3(3,2) > D3(3,4) + D3(4,2), D4(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 D4 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.