Nearest Neighbour

The Nearest Neighbour Algorithm works as follows:

1. Choose any city as a starting point. Call this city 'a'.
2. Visit the nearest city to city 'a', which we shall call city 'b'. City 'b' becomes the 'current city'.
3. Visit the nearest city to city 'b' which has not yet been visited - city 'c'. City 'c' is now the 'current city'.
4. As per point 3, repeatedly visit the nearest unvisited city to the current city until all cities have been visited once.
5. Once all cities have been visited once, return from the last city to have been visited to the starting city - city 'a'.

Choose your starting city (shown in green). This will also be the final destination.	Find the closest city to your starting city (red).
Draw a line between the two. Now locate the nearest unvisited city to the newly incorporated city of the previous step.	Once again,draw a line between the two, then locate the nearest unvisited city to the newly incorporated city of the previous step.
Repeat Step 3/4...	...until only one city remains unvisited...
...and once this is incorporated...	..the only option is to return to the starting city.

Previous Back to Top Next