4 The table defines a network on 6 nodes, the numbers representing distances between those nodes.
| A | B | C | D | E | F |
| A | | 3 | 2 | 7 | 8 | 3 |
| B | 3 | | 4 | 5 | | |
| C | 2 | 4 | | | 6 | |
| D | 7 | 5 | | | | |
| E | 8 | | 6 | | | 2 |
| F | 3 | | | | 2 | |
- Use Dijkstra's algorithm to find the shortest routes from A to each of the other vertices. Give those routes and their lengths.
- Jack wants to find a minimum spanning tree for the network.
- Apply Prim's algorithm to the network, draw the minimum spanning tree and give its length.
Jill suggests the following algorithm is easier.
Step 1 Remove an arc of longest length which does not disconnect the network
Step 2 If there is an arc which can be removed without disconnecting the network then go to Step 1
Step 3 Stop - Show the order in which arcs are removed when Jill's algorithm is applied to the network.
- Explain why Jill's algorithm always produces a minimum spanning tree for a connected network.
- In a complete network on \(n\) vertices there are \(\frac { n ( n - 1 ) } { 2 }\) arcs. There are \(n - 1\) arcs to include when using Prim's algorithm. How many arcs are there to remove using Jill's algorithm?
For what values of \(n\) does Jill have more arcs to remove than Prim has to include?