TSP upper bound: nearest neighbour

The algorithm

1. Choose a starting vertex.

2. From the current vertex, travel to the nearest vertex not yet visited.

3. Repeat until every vertex has been visited.

4. Return directly to the start.

Using a table

In a distance table, look along the row (or down the column) of the current vertex for the smallest entry in a column not yet used. Write the tour in order, for example A B C D E A, and add the lengths.

Different starts

Different starting vertices often give different tours. Running the algorithm from each vertex and keeping the shortest tour gives the best upper bound from this method. On a table of shortest distances, translate the tour back to the original network when asked (for example, a table entry QS may mean the route Q R S).

Not Prim

Nearest neighbour always moves on from the last vertex reached and finishes by returning to the start. Prim adds the shortest edge from any vertex in the tree and makes a tree, not a tour.

Worked example

Apply nearest neighbour to table T starting at C.

1. From C nearest unvisited is D (9); from D, E (11); from E, B (14); from B, A (12); return A to C (18).

Answer: Tour CDEBAC, length 64

Check yourself

1. Use the nearest neighbour algorithm starting at A to find an upper bound for table T.
   Show answer

   62. Tour ABCDEA: 12 + 10 + 9 + 11 + 20 = 62.

2. Apply nearest neighbour to table T starting at E. What is the tour?
   • EDCBAE
   • EDCABE
   • EBCDAE
   • EDBCAE
   Show answer

   EDCBAE. E to D (11), D to C (9), C to B (10), B to A (12), A to E (20).

3. Nearest neighbour is applied to table T from every vertex. What is the best upper bound found?
   Show answer

   62. Tours: A: ABCDEA = 62; B: BCDEAB = 62; C: CDEBAC = 64; D: DCBAED = 62; E: EDCBAE = 62. Best 62.

4. What is the length of the nearest neighbour tour from C for table T?
   Show answer

   64. CDEBAC = 9 + 11 + 14 + 12 + 18 = 64.

5. What is the key difference between nearest neighbour and Prim's algorithm?
   • Nearest neighbour chooses the longest edge
   • Prim's algorithm returns to the start
   • Prim's algorithm needs a complete network
   • Nearest neighbour extends only from the last vertex visited
   Show answer

   Nearest neighbour extends only from the last vertex visited. Prim extends from any vertex in the tree; nearest neighbour only from the current end of the route.

6. Why is a nearest neighbour tour length an upper bound and not the answer?
   • It is always longer than the optimum
   • The tour is a real tour but is not guaranteed to be the shortest
   • It skips some vertices
   • It may not return to the start
   Show answer

   The tour is a real tour but is not guaranteed to be the shortest. Nearest neighbour is greedy: early cheap choices can force expensive later ones, such as a long return edge.

Practise with instant feedback Print this lesson

Sources

• Pearson Edexcel International Advanced Level in Mathematics specification (issue 3)
• Pearson Edexcel IAL Decision Mathematics 1 scheme of work

Last updated 7 November 2026. Spotted a mistake? Tell us.