Search code examples
pythonnetworkxtraveling-salesman

How to get sorted list of nodes for a list of nodes in a NetworkX graph as approximation of TSP

I have an undirected NetworkX graph (not necessarily complete, but connected). Also, I have a list of few nodes from all nodes of the above graph. I want to get the travel distance as per TSP result(or it's approximation).

I tried using networkx.approximation.traveling_salesman_problem(DS.G, nodes=['A0_S0_R0', 'A0_S14_R4', 'A0_S4_R4', 'A0_S14_R4', 'A0_S14_R4', 'A0_S7_R4']), but output list is a list of nodes to be used to cover given nodes in the order they appear in the given input list.

I want either total minimised distance or list of nodes in the order such that travelling distance is minimised and not according to their appearance in the input list.

Solution

  • The tsp function will return the list of nodes corresponding to best found path.

    You can get the minimum distance using

    nodes = [...] # list of nodes returned by traveling_salesman_problem()
# assuming you used `weight` key for edge weights
distances = [G.get_edge_data(nodes[i],node[i+1])['weight'] for i in range(len(nodes)-1)]
min_distance = sum(distances)