Problem

The table shows the distances, in km, between eight towns, A, B, C, D, E, F, G, H and J.

	A	B	C	D	E	F	G	H	J
A	–	15	7	25	15	42	64	51	46
B	15	–	22	40	30	57	49	36	31
C	7	22	–	32	22	49	71	58	53
D	25	40	32	–	10	17	57	70	71
E	15	30	22	10	–	27	67	66	61
F	42	57	49	17	27	–	40	53	72
G	64	49	71	57	67	40	–	13	32
H	51	36	58	70	66	53	13	–	19
J	46	31	53	71	61	72	32	19	–

A van driver must visit each town at least once, starting and finishing at A. The driver wishes to minimise the total distance travelled.

(a) Use Prim’s algorithm, starting at A, to obtain a minimum spanning tree for the network. You must clearly state the order in which you select the arcs.

(b) Use your answer to part (a) to determine an initial upper bound for the length of the van driver’s route.

(c) Use the nearest neighbour algorithm, starting at A, to find another upper bound for the length of the van driver’s route. Write down the route that gives this upper bound.

(d) By deleting A and all of its arcs, and using the answer to part (a), obtain a lower bound for the length of the van driver’s route.

(e) State the smallest interval that must contain the optimal length of the van driver’s route.

(f) State, with a reason, which of the upper bounds found in parts (b) and (c) is the better upper bound.

(g) Determine the length of an optimal route for the van driver. You must justify your answer.