Question $2$: Floyd$-$Warshall Algorithm

Problem Statement

Consider a network of cities connected by direct roads in Figure $2.$ Each road has a specific travel time associated with it$.$ Given the following weighted graph representing the travel times between cities, use the Floyd$-$Warshall algorithm to find the shortest travel time between all pairs of cities.

Graph

The cities and the direct travel times between them are shown in the graph below:

Figure $2$: Graph $2$

Instructions $($Show detailed work$)$

$1.$ Construct the initial adjacency matrix for this graph, where the value at position $\backslash (($i$,$ j$)\backslash )$ represents the travel time from city $\backslash ($ i $\backslash )$ to city $\backslash ($ j $\backslash ),$ and use $\backslash (\backslash$infty $\backslash )$ for pairs of cities without a direct road.

$2.$ Apply the Floyd$-$Warshall algorithm to update the matrix and find the shortest travel time between every pair of cities.

$3.$ Provide each updated matrix as you pass through each intermediate node.