TSP Nearest-Neighbor Tour

Problem

Build a TSP tour with the nearest-neighbor heuristic. dist is a symmetric n by n matrix of travel costs.

Start at city 0 and repeatedly move to the closest unvisited city, breaking ties by the smallest index, and finally return from the last city to city 0. Return [tour, total_cost] where tour lists the cities in visited order.

Hint

Greedily pick the cheapest unvisited city at each step, then close the loop.

Test cases

case 1

in: [[[0,1,4,5],[1,0,2,3],[4,2,0,1],[5,3,1,0]]]

expected: [[0,1,2,3],9]

case 2

in: [[[0]]]

expected: [[0],0]

case 3

in: [[[0,3],[3,0]]]

expected: [[0,1],6]

case 4

in: [[[0,3,4,5,2],[3,0,2,6,3],[4,2,0,1,5],[5,6,1,0,4],[2,3,5,4,0]]]

expected: [[0,4,1,2,3],13]

Starter codePython

def tsp_nearest_neighbor(dist):
    # Your code here
    pass

4 test cases · run your code against them in the editor