El algoritmo del vecino más cercano fue uno de los primeros algoritmos utilizados para resolver aproximadamente el problema del viajante de comercio. En ese problema, el vendedor comienza en una ciudad al azar y visita repetidamente la ciudad más cercana hasta que haya visitado todas. El algoritmo produce rápidamente un recorrido corto, pero por lo general no es el óptimo.
El algoritmo del vecino más cercano es fácil de implementar y se ejecuta rápidamente, pero a veces puede pasar por alto rutas más cortas que se notan fácilmente con la percepción humana, debido a su naturaleza "codiciosa". Como guía general, si las últimas etapas del recorrido son comparables en duración a las primeras etapas, entonces el recorrido es razonable; si son mucho mayores, entonces es probable que existan recorridos mucho mejores. Otra verificación es usar un algoritmo como el algoritmo de límite inferior para estimar si este recorrido es lo suficientemente bueno.
En el peor de los casos, el algoritmo da como resultado un recorrido que es mucho más largo que el recorrido óptimo. Para ser precisos, para cada constante r existe una instancia del problema del viajante de comercio tal que la duración del recorrido calculado por el algoritmo del vecino más cercano es mayor que r veces la duración del recorrido óptimo. Además, para cada número de ciudades hay una asignación de distancias entre las ciudades para las cuales la heurística del vecino más cercano produce el único peor recorrido posible. (Si el algoritmo se aplica en cada vértice como el vértice inicial, la mejor ruta encontrada será mejor que al menos N/2-1 otros recorridos, donde N es el número de vértices). [1]