Shortest Path to Cover All nodes in a graph given a starting and ending node

Question

I am trying to solve a problem in which there is an undirected graph with positive weighted edges and I need to find the shortest path that covers all the nodes exactly once given the start and end node. In addition the graph is complete(each node is connected to all the other nodes in the graph). I have tried searching for an algorithm that could solve this problem but I haven't found one that solves this problem. This is not exactly the traveling sales man problem because of the restriction of the start and end node. I will appreciate any kind of help.

Answer 1

If you're starting at node S and ending at T, add a dummy node D that has zero-weight edges to only S and T. Find an optimal travelling salesman tour on this graph, then remove the dummy node from the tour to get your path.

If you'd like to preserve the graph's completeness property, you can implement the above by adding the dummy node with zero-weight edges to S and T, and with edges to all other nodes having weights larger than the sum of the weights of the n heaviest edges in the graph. For practical purposes, this means setting their weights to Integer.Max or similar.