The 'travelling salesman problem' is, for a given network of vertices connected by arcs of given lengths, to find the minimum distance that visits each vertex once and returns to the starting vertex.
For a small network, it is possible to find the minimum distance by examining every possible route, but as the size of the network grows, so does the number of routes that must be examined. It is helpful to find upper and lower bounds for the minimum distance.
An upper bound can easily be found by doubling the length of the minimum spanning tree, but a better, lesser, estimate can be found using the Nearest Neighbour Algorithm:
-
Choose a starting vertex
-
Move from the present vertex to the nearest vertex not yet visited.
-
Repeat 2. Until every vertex has been visited. Return to the start vertex.
For example, choose A as the starting vertex.
The nearest vertex to A is B, distance 5.
The nearest vertex to B, apart from A is E, distance 1.
The nearest vertex to E, apart from A or B, is C, distance 3.
The nearest vertex to C, apart from A, B or E, is D, distance 2.
The quickest route from D to A is the direct one, distance 6.
An upper bound for the minimum distance for this network is 5+1+3+2+6=17.