Nearest Neighbor Algorithm — Definition, Formula & Examples

The nearest neighbor algorithm is a quick way to plan a round trip through every city on a map. From wherever you are, you travel to the closest place you have not visited yet, and once every place is visited you return to the start.

Let $G=(V,E,w)$ be a complete weighted graph with $n$ vertices and a chosen start vertex $v_0$ . The algorithm builds a Hamiltonian cycle $v_0, v_1, \dots, v_{n-1}, v_0$ . At each step, $v_{k+1}$ is chosen to minimize $w(v_k, u)$ over all unvisited vertices $u$ , with ties broken arbitrarily. It is a greedy heuristic for the Traveling Salesman Problem (TSP). It runs in $O(n^2)$ time but does not guarantee a minimum-weight cycle.

Worked Example

Problem: A complete graph has vertices A, B, C, D with edge weights AB = 1, AC = 4, AD = 10, BC = 2, BD = 5, CD = 3. Use the nearest neighbor algorithm starting at A. Find the tour and its total weight, then compare it with the shortest possible tour.

Step 1: Start at A. The edges to unvisited vertices are AB = 1, AC = 4, AD = 10. The smallest is AB, so move to B.

\min(1, 4, 10) = 1

Step 2: From B, the unvisited vertices are C and D, with BC = 2 and BD = 5. Move to C.

\min(2, 5) = 2

Step 3: From C, only D remains, so take CD = 3. Every vertex is now visited, so add the return edge DA = 10.

1 + 2 + 3 + 10 = 16

Answer: The nearest neighbor tour is A → B → C → D → A, with total weight 16. A complete graph on 4 vertices has only

(4-1)!/2 = 3

distinct tours, so you can check them all. The tour A → B → D → C → A has weight

1 + 5 + 3 + 4 = 13

. The greedy choices forced the costly final edge DA = 10, so the algorithm missed the optimal tour.

Why It Matters

Checking every tour takes

(n-1)!/2

cycles, which is far too many even for 20 cities. Nearest neighbor gives a usable tour in seconds. Delivery-routing software and circuit-board drilling planners often use it as a starting tour, then improve it with methods such as 2-opt. In a discrete math course, it is also the standard example of a greedy algorithm that can fail to find the best answer.

Common Mistakes

Mistake: Stopping after the last new vertex and forgetting the edge back to the start.

Correction: A TSP tour is a cycle, so you must add the return edge. In the example, leaving out DA = 10 would report 6 instead of 16 and hide why the tour is poor.

Related Terms

Algorithm — the broader concept this term builds on
Bipartite Graph — Another graph structure studied alongside routing problems
Acyclic Graph — Contrast: the algorithm's output is always a cycle
Pseudograph — Graphs with loops and multi-edges, excluded here
Cayley Graph — Graphs where Hamiltonian cycles are actively studied