Nearest Neighbor   <-   TSP Generator   <-   Research   <-   Sean Forman   <-   You Are Here

# Explanation of the Nearest Neighbor Algorithm

The nearest neighbor algorithm and the closely related repetitive nearest neighbor algorithm is a greedy algorithm for finding candidate solutions to the traveling salesman problem. The nearest neighbor algorithm begins at the first city in your list of cities to visit. It then selects the closest city to visit next. From the remaining unvisited cities it selects the city closest to city two and so on.

## For example

```                       |     1     2     3     4     5  |     6     7     8
-----------------------+--------------------------------+-------------------
1 Chicago IL          |          672   848  1737   954 |   1195  1850   906
2 Philadelphia PA     |    672         255  2383  1368 |   1047  2520  1572
3 Boston MA           |    848   255        2489  1617 |   1270  2689  1753
4 Seattle WA          |   1737  2383  2489        1891 |   2732   708  1033
5 Houston TX          |    954  1368  1617  1891       |    967  1615   871
-----------------------+--------------------------------+-------------------
6 Miami FL            |   1195  1047  1270  2732   967 |         2565  1710
7 Palo Alto CA        |   1850  2520  2689   708  1615 |   2565         952
8 Denver CO           |    906  1572  1753  1033   871 |   1710   952
```

Beginning in Chicago, we choose the closest city, Philadelphia (2) to visit next. Once in Philly, we can't return to Chicago, but Boston (3) is closer anyway, so we go there. In Boston, we now can't go to Chicago or Philly. Continuing this way we get the route.

```ROUTE BY NEAREST NEIGHBOR:
Chicago, IL                ->  Philadelphia, PA              672
Philadelphia, PA           ->  Boston, MA                    255
Boston, MA                 ->  Miami, FL                    1270
Miami, FL                  ->  Houston, TX                   967
Houston, TX                ->  Denver, CO                    871
Denver, CO                 ->  Palo Alto, CA                 952
Palo Alto, CA              ->  Seattle, WA                   708
Seattle, WA                ->  Chicago, IL                  1737
------
DISTANCE:                                                      7432
```

In repetitive nearest neighbor, we generate a route using the nearest neighbor algorithm for each city in our list, and then select the shortest route from our choices.

```DISTANCES BY NEAREST NEIGHBOR BEGINNING AT:
Chicago, IL                   7432