Nearest Neighbour Algorithm

  1. Start at a Home Vertex,

  2. Whenever your are at a vertex, pick the next nearest unvisited vertex (neighbour). In case of a tie, don't worry; pick the one you like,

  3. Go back to your Home Vertex.

Here's how it works with the following weighted graph

Let's assume that our home-vertex is A. It starts by going from A to D, from D it goes to E, from E to C from C to B and then finaly from B to A. Below the circuit is marked with the boldface edges. When we calculate the weight of this circuit, A-D-E-C-B-A, we get: 185 + 302 + 165 + 305 + 500 = 1457. Note that this method, though efficient is not necessarily optimal.


Repetitive Nearest Neighbour