Nearest-Neighbor Tour Construction

The Nearest-Neighbor Rule

A traveling-salesperson tour must visit every vertex once and return to its starting point. On a weighted complete graph, every possible move between distinct vertices is available, but the number of possible tours can grow quickly. The nearest-neighbor algorithm constructs a tour by making a local choice at each step: from the current vertex, go to a closest vertex that has not yet been visited. The rule is simple to execute; it does not, by itself, certify that the tour has minimum cost.

Throughout, let \(G=(V,E)\) be a finite, simple, undirected complete graph with \(n=|V|\ge 3\). Each edge \(uv\in E\) has a nonnegative real weight \(w(uv)=w(vu)\). Completeness means that every pair of distinct vertices is joined by an edge. A tour is a cyclic ordering of all \(n\) distinct vertices, with an edge between each consecutive pair and an edge from the last vertex back to the first. Its cost is the sum of the weights of those \(n\) edges.

The choice is always made from the unvisited vertices only. In particular, the algorithm does not close the tour early by returning to the start; the return edge is added after every vertex has been visited. This distinction separates constructing the path through the vertices from closing that path into a tour.

Procedure and Correctness

The algorithm can be recorded as a sequence \(v_1,v_2,\ldots,v_n\), where \(v_1=s\). For each \(i\) with \(1\le i<n\), choose \(v_{i+1}\) among \(V\setminus\{v_1,\ldots,v_i\}\) to minimize \(w(v_iv_{i+1})\). The output tour is \(v_1v_2\cdots v_nv_1\), and its cost is

Proof. Fix a start \(v_1=s\). We show that after \(i\) choices of visited vertices, the algorithm has a list of \(i\) distinct vertices, and each successive pair in the list is joined by an edge. This holds initially for the one-vertex list \(v_1\). Suppose it holds for some \(i<n\). Since the list contains \(i<n\) distinct members of \(V\), the set \(V\setminus\{v_1,\ldots,v_i\}\) is nonempty. Choose \(v_{i+1}\) from that set according to the minimum-weight rule. It is distinct from every earlier listed vertex, and completeness guarantees the edge \(v_iv_{i+1}\). Thus the list can be extended by one distinct vertex and remains joined by edges at consecutive positions. Repeating this argument reaches a list of \(n\) distinct vertices, which contains all of \(V\). Completeness also guarantees the edge \(v_nv_1\). Adding it gives a closed cycle through all vertices exactly once, as required. \(\square\)

This result guarantees validity, not optimality. At each step the algorithm minimizes the cost of its next edge among the currently available choices. It does not compare the full future costs of the different possible choices. The final return edge is included in the tour cost even though it is not selected by a nearest-neighbor decision.

Tracing the Choices

In an implementation, keep a set of visited vertices and a current vertex. At each iteration, scan the unvisited vertices, compare their edge weights from the current vertex, and append a minimum-weight candidate to the route. After \(n-1\) moves from the start, add the return edge. If the weights are stored in a table, scanning all candidates takes at most \(n-1\) comparisons in the first iteration, then \(n-2\), continuing down to \(1\). The total number of such comparisons is \((n-1)+(n-2)+\cdots+1=n(n-1)/2\), so this direct implementation takes \(O(n^2)\) comparisons. This count concerns the selection scans; the final return-edge lookup adds only one more weight lookup.

Short and Longer Traces

Common Pitfalls and Interpretation

Forgetting the return edge. In the five-vertex example, the selected path edges have total weight \(2+3+4+2=11\). Reporting \(11\) as the tour cost is wrong because the tour must return from \(E\) to \(A\). The closing edge has weight \(7\), so the correct total is \(11+7=18\).

Choosing from the wrong set. The next vertex must be unvisited. For example, after moving from \(A\) to \(B\) in the five-vertex example, the algorithm compares \(BC=3\), \(BD=6\), and \(BE=5\); it does not consider \(BA\), because \(A\) is already visited. Reconsidering a visited vertex would fail to extend the list of distinct vertices and could prevent the procedure from constructing a tour.

Confusing a locally closest move with a global optimum. In the four-vertex example, the first two choices are forced by the nearest-neighbor rule: \(A\) to \(B\), then \(B\) to \(C\). Those choices lead to the expensive edge \(CD\), giving cost \(112\). A different tour has cost \(15\). The algorithm's stated rule concerns the next edge, not the total cost of all possible tours.

The method is useful when a tour is needed quickly and a simple, reproducible construction is more important than proving optimality. Its output can also serve as a concrete tour whose cost can be compared with a lower bound or with other candidate tours. To interpret a result correctly, record the specified start, the sequence of chosen vertices, the closing edge, and the sum of all \(n\) edge weights. When ties occur, the rule allows any minimum-weight candidate; the particular resulting route depends on which tied candidate is selected.