The nearest neighbour algorithm produces a complete travelling salesman tour and calculates its total weight. Because this is a feasible tour, its weight is an upper bound for the unknown optimal tour.
This is HL-only content from AHL 3.16: Tree and cycle algorithms, Chinese postman, travelling salesman. The example below uses an HL Paper 1 short-response style.
How the algorithm works
Starting from a chosen vertex:
- Travel to the nearest unvisited vertex.
- From that vertex, again travel to the nearest unvisited vertex.
- Continue until every vertex has been visited exactly once.
- Return to the starting vertex to complete a Hamiltonian cycle.
- Add the weights of all selected edges.
Before starting, check that the weighted graph is complete, or that the table gives the least available distance between every pair of vertices. If there is a tie for the nearest unvisited vertex, state which tied edge you choose and continue consistently. Repeating from another starting vertex can improve the bound but does not prove optimality.
For example, suppose the relevant edge weights are:
| Edge | Weight |
|---|---|
Starting at , nearest neighbour gives the tour
Its total weight is
Therefore, if the optimal tour has weight , then
The common misconception is that nearest neighbour always finds the minimum tour. It does not: choosing the cheapest edge at each stage is a greedy algorithm, so an early choice can force an expensive edge later. Different starting vertices may produce different tours; when instructed to repeat the algorithm, use each possible starting vertex and take the smallest resulting upper bound.
Exam technique
In an IB response, show the starting vertex, the order in which vertices are visited, the return edge, and the total weight. State explicitly that the result is an upper bound because it is the weight of a valid complete tour, not because it has been proven optimal.
