Question

There are five cities in a network. The cost of building a road directly between i and j is the entry ai,j in the matrix below. An infinite entry indicates that there is a mountain in the way and the road cannot be built. Determine the least cost of making all the cities reachable from each other.

0 3 5 11 9
3 0 3 9 8
5 3 0 [infinity] 10
11 9 [infinity] 0 7
9 9 10 7 0

Answer 1

Given :

There are five cities in a network and the cost of
`\text{building}` a road directly between
`i` and
`j` is the entry
`a_(i,j)`

`a_(i,j)` refers to the matrix.

Road cannot be built because there is a mountain.

The given matrix :

`\begin{bmatrix}0 & 3 & 5 & 11 & 9\\ 3 & 0 & 3 & 9 & 8\\ 5 & 3 & 0 & \infty & 10\\ 11 & 9 & \infty & 0 & 7\\ 9 & 8 & 10 & 7 & 0\end{bmatrix}`

The matrix on the left above corresponds to the weighted graph on the right.

Using the
`\text{Kruskal's algorithm}` we can select the cheapest edge that is not creating a cycle.

Starting with 2 edges of weight 3 and the edge of weight 5 is forbidden but the edge is 7 is available.

The edge of the weight 8 completes a minimum spanning tree and total weight 21.

If the edge of weight 8 had weight 10 then either of the edges of weight 9 could be chosen the complete the tree and in this case there could be 2 spanning trees with minimum value.