Edit Article

Edited by Caidoz, Flickety, Livorde, Marysharyclary and 5 others

The nearest neighbour algorithm works in a similar way to Prim's algorithm, but instead of finding a tree you find a path around your graph/network.

Ad

Edit Steps

  1. 1
    Choose a node.
    Ad
  2. 2
    From that node choose the arc of least weight joining it to another node.
  3. 3
    From the node you have connected to (not the one you started off with), find the arc of least weight which will not create a cycle (loop) and add it to your path.
  4. 4
    Continue in this manner until all of the nodes are connected.
  5. 5
    Once all of the nodes are connected, join the first and last node with the minimum arc connecting them, and this completes the cycle around your network.
    Ad

Edit Warnings

  • Sometimes this method will cut your graph in half, making it impossible to complete the path.
  • This method does not always result in the best solution.

Edit Related wikiHows

How to
Use Dijkstra's Algorithm

How to
Use the Chinese Postman Algorithm

How to
Find the Minimum Spanning Tree of a Graph

Article Info

Categories: Mathematics

Recent edits by: Praveen Piyush, Juan, Buddhalover101

Ad

Thanks to all authors for creating a page that has been read 9,573 times.

Was this article accurate?

YesNo
x

Thank Our Volunteer Authors.

Follow us on Google+