6 The matrix gives the lengths of the arcs of a network.
| A | B | C | D | E | F |
| A | - | 10 | 7 | - | 9 | 5 |
| B | 10 | - | - | 1 | - | 4 |
| C | 7 | - | - | - | 3 | - |
| D | - | 1 | - | - | 2 | - |
| E | 9 | - | 3 | 2 | - | - |
| F | 5 | 4 | - | - | - | - |
- Using the copy of the matrix in your answer book, apply the tabular form of Prim's algorithm to find a minimum connector for the network. Start by choosing vertex A and show the order in which you include vertices.
List the arcs in your connector and give its total length.
Serena takes a different approach to find a minimum connector. She first uses Dijkstra's algorithm to find shortest paths from A to each of the other vertices. She then uses the arcs in those paths to construct a connector. - Draw the network using the vertices printed in your answer book.
- Apply Serena's method to produce a connector.
List the arcs in the connector and give its total length.
Serena adapts her method by starting from each vertex in turn, producing six connectors, from which she chooses the best.
- Serena's approach will not find the minimum connector in all networks, but it is an algorithm. What is its algorithmic complexity? Justify your answer.