Double Tree TSP Tour Cost

Problem

Build the double-tree 2-approximation tour for a metric TSP instance and return its cost.

Prim builds a minimum spanning tree with smallest-index tie-breaking, a preorder depth-first traversal gives the visit order, and the tour cost closes back to the start. dist is a symmetric distance matrix; return 0 for fewer than two cities.

Hint

A preorder walk of the MST visits every vertex and, by the triangle inequality, never costs more than twice the tree.

Test cases

case 1

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

expected: 6

case 2

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

expected: 8

case 3

in: [[[0,10,15,20],[10,0,35,25],[15,35,0,30],[20,25,30,0]]]

expected: 95

case 4

in: [[[0]]]

expected: 0

case 5

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

expected: 6

Starter codePython

def double_tree_tour_cost(dist):
    # Your code here
    pass

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