5 Answer this question on the insert provided.
Table 5 specifies a road network connecting 7 towns, A, B, \(\ldots\), G. The entries in Table 5 give the distances in miles between towns which are connected directly by roads.
\begin{table}[h]
| A | B | C | D | E | F | G |
| A | - | 10 | - | - | - | 12 | 15 |
| B | 10 | - | 15 | 20 | - | - | 8 |
| C | - | 15 | - | 7 | - | - | 11 |
| D | - | 20 | 7 | - | 20 | - | 13 |
| E | - | - | - | 20 | - | 17 | 9 |
| F | 12 | - | - | - | 17 | - | 13 |
| G | 15 | 8 | 11 | 13 | 9 | 13 | - |
\captionsetup{labelformat=empty}
\caption{Table 5}
\end{table}
- Using the copy of Table 5 in the insert, apply the tabular form of Prim's algorithm to the network, starting at vertex A. Show the order in which you connect the vertices.
Draw the resulting tree, give its total length and describe a practical application.
- The network in the insert shows the information in Table 5. Apply Dijkstra's algorithm to find the shortest route from A to E.
Give your route and its length.
- A tunnel is built through a hill between A and B , shortening the distance between A and B to 6 miles. How does this affect your answers to parts (i) and (ii)?