Suppose I have a list=[2,5,7] (representing a visit order of cities). I want to insert node 6 to this list (or Graph); however, I'm looking for the best place of insertion (in terms of total cost of list). For instance Cost of list1=[2,6,5,7] is lower than cost of list2=[2,5,7,6]. The Cost function is the distance between nodes. For instance, Cost[2,6,5,7] = Distance[2][6] + Distance[6][5] + Distance[5][7]
Is there any fast way of doing this? Is there any built-in function in Networkx (like nx.dijkstra_path_length(G, i, j, 'weight') which calculates shortest path before insertion) or any other package? Please note that list=[2,5,7] can be considered as a graph and easily generated by Networkx (2---5---7)
P.S: I will provide a toy-sized instance below: a=[6,10] and list=[2,5,7] are my inputs. I want to add all nodes in a (6 and 10) to the best places in list (like adding a node to a TSP tour). There are two possible positions for insertion of 6 in list.
A: between 2 and 5
B: between 5 and 7.
Since Cost[2,6,5,7] < Cost[2,5,7,6], option A provides lowest cost.
Now list=[2,6,5,7].
Again for insertion of node 10, all three possible places should be checked
A: between 2 and 6
B: between 6 and 5
C: between 5 and 7.
Output would be a list like [2,6,5,10,7]