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.