Nearest neighbour

Nearest neighbour is a greedy algorithm initially to find the shortest path among a graph. It is typically used to solve problems like Traveling Salesman.

It basically works like Prim's algorithm, but the next nearest vertice needs to be connected to the last one.

Complexity

Time complexity

• Worst case: $O(n^2)$
• Best case: $\mathrm{\Omega }(n^2)$