EXAMPLE 3 Applying the Nearest-Neighbor Algorithm

Applying this algorithm to the TSP in Figure 2.3 quickly leads to the tour of Chicago, St. Louis, Cleveland, Minneapolis, and Chicago, with a length of 2040 miles. Here is how this tour is determined. Because we are starting in Chicago, there is a choice of going to a city that is 425, 300, or 349 miles away. Because the smallest of these numbers is 300, we next visit St. Louis, which is the nearest neighbor of Chicago not already visited. At St. Louis, we have a choice of visiting next cities that are 541 or 562 miles away. Hence, Cleveland, which is nearer (541 miles), is visited. To complete the tour, we visit Minneapolis and return to Chicago, thereby adding 774 and 425 miles to the length of the tour. The total length of the tour is 2040 miles.