The nearest neighbour algorithm was one of the first algorithms used to determine a solution to the traveling salesman problem, and usually comes to within 20% of the optimal route.

These are the steps of the algorithm:

1. Pick an arbitrary starting vertex.
2. If the current vertex has no unmarked edges, terminate.
3. Find the unmarked edge from the current vertex with the least weight and mark it.
4. Select the vertex at the other end of the edge.
5. Repeat from step 2.

The order in which the vertices are visited is the output of the algorithm.

The nearest neighbour algorithm is easy to implement and executes quickly, but it can sometimes miss shorter routes which are easily noticed with human insight. The result of the nearest neighbour algorithm should be checked before use, just in case such a shorter route has been missed.

In the worst case, the algorithm can compute tours that are by an arbitrary factor larger than the optimal tour. To be precise, for every constant r there is an instance of the traveling salesman problem such that the length of the tour computed by the nearest neighbour algorithm is greater than or equal to r times the length of the optimal tour.

Graph algorithms

Nearest-Neighbor-Heuristik | Thuật toán láng giềng gần nhất