The nearest neighbor algorithm, also called the nearest neighbor heuristic, is a greedy algorithm for constructing a tour in the traveling salesman problem when a distance is given between every pair of cities. Starting at a chosen city, it repeatedly visits the closest unvisited city and returns to the starting city after all cities have been visited. Ties can be resolved by a fixed ordering of the cities (Cook 2012, pp. 65-67).
The resulting Hamiltonian cycle need not be shortest, and the tour can depend on the starting city and the resolution of ties.
Trying each starting city and retaining the shortest of the resulting tours can improve
the result but does not guarantee an optimal tour. With precomputed distances, a
straightforward implementation from one starting city uses 
distance comparisons for 
cities.
For symmetric distances satisfying the triangle inequality, the worst-case ratio of the tour length to the optimum grows logarithmically with the number of cities (Rosenkrantz et al. 1977). The algorithm is distinct from the nearest neighbor problem in computational geometry, which asks for the closest point to a specified query point rather than for a tour.
