I have a "small-scale" TSP problem where exact solution can be trivially computed as follows. I am trying to get this to work by spitting out "all source" TSP paths. I don't have to start at a fixed node. I can start any where, and want to know all possible optimal paths from each vertex. How can this be done other than having to generate multiple distance matrices re-labeling the vertices each time, which would be quite annoying.
import numpy as np
from python_tsp.exact import solve_tsp_dynamic_programming
distance_matrix = np.array([
[0,437,23,21,41,300,142,187,81,171,98],
[545,0,10,19,54,339,142,201,78,170,143],
[95,147,0,186,273,93,29,55,731,76,164],
[45,60,930,0,518,28,10,13,298,31,71],
[74,111,495,490,0,62,25,21,407,87,143],
[122,126,2,1,13,0,2057,241,17,45,26],
[328,313,5,20,34,527,0,560,70,107,76],
[208,200,5,9,24,442,159,0,41,61,41],
[122,174,53,44,110,98,25,40,0,878,798],
[214,340,12,37,66,162,54,96,199,0,789],
[265,423,12,27,90,173,73,86,312,701,0]])
distance_matrix = distance_matrix * -1
solve_tsp_dynamic_programming(distance_matrix)
([0, 5, 6, 7, 4, 3, 2, 8, 9, 10, 1], np.int64(-7727))
NOTE: I only want exact solutions, and not approximations.
Add a fake start node that has a huge distance to all other nodes except your chosen start which will have a distance of 0 such that fake start to desired start is always the optimal first step. Keep the return distances 0. Then do a manual correction for the return trip distance.
distance_matrix = np.array([
[0,437,23,21,41,300,142,187,81,171,98],
[545,0,10,19,54,339,142,201,78,170,143],
[95,147,0,186,273,93,29,55,731,76,164],
[45,60,930,0,518,28,10,13,298,31,71],
[74,111,495,490,0,62,25,21,407,87,143],
[122,126,2,1,13,0,2057,241,17,45,26],
[328,313,5,20,34,527,0,560,70,107,76],
[208,200,5,9,24,442,159,0,41,61,41],
[122,174,53,44,110,98,25,40,0,878,798],
[214,340,12,37,66,162,54,96,199,0,789],
[265,423,12,27,90,173,73,86,312,701,0]])
nodes = distance_matrix.shape[0]
dm2 = np.zeros((nodes + 1, nodes + 1))
dm2[1:, 1:] = distance_matrix
# If you want a specific start ############
dm2[0] = 999_999
start = 3 # Keep in mind there's an offset by 1
dm2[0, start] = 0
###########################################
dm2 *= -1
route, distance = solve_tsp_dynamic_programming(dm2)
correction = dm2[route[-1], route[1]]
This is if you want to know the optimal path for each specific start. However, if you just want the optimal path without a specific start, simply have the fake start be 0 distance from everywhere else.