Given an undirected weighted graph where an edge exists between every pair of nodes (n1,n2) with cost C(n1,n2), find the shortest path (possibly revisiting nodes, possibly revisiting edges) through the graph that visits each node. Algo can pick any source node it wants. No need for the path to terminate back at the source node. Path cost is cumulative over all edge visits, so, if you traverse an edge with cost 5 and then traverse it again later it costs you 10 (i.e. re-traversing an already explored edge isn't free!)
$\begingroup$
$\endgroup$
4
-
5$\begingroup$ I don't know how it is called, but it seems NP-hard. You can show a reduction from Hamiltonian Path to this problem (give edges in the original graph cost $1$ and cost $n$ to edges not in the original graph; then your problem has a solution of cost $n-1$ iff the original graph had a Hamiltonian path). $\endgroup$– Karolina SołtysCommented Apr 29, 2011 at 17:15
-
2$\begingroup$ Travelling salesman problem? $\endgroup$– Pratik DeoghareCommented Apr 29, 2011 at 17:31
-
$\begingroup$ @MachineCharmer TSP doesn't allow node revisiting. $\endgroup$– DejasCommented Apr 29, 2011 at 18:03
-
4$\begingroup$ a minor terminological note --- a 'path' which can revisit nodes (or edges) is called a walk; "paths" are usually defined to exclude revisiting nodes. $\endgroup$– Niel de BeaudrapCommented May 1, 2011 at 2:29
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
12
The TSP problem, given a graph and an edge-weight function, asks to find a tour visiting each vertex exactly once having minimum length.
I think your problem is equivalent to the Metric TSP problem, that is the TSP problem on the complete graph where the weight of each edge $uv$ is the length of a path between $u$ and $v$ with minimum weight in your original graph.
Indeed, a minimum walk on your original graph corresponds to a minimum tour in the newly defined clique, and vice-versa.
For the first side, consider a minimum walk in the original graph. If some node is repeated (say $v$ is repeated: $\ldots, v, \ldots, u, v, w, \ldots$) one can get rid of the repetition by replacing the portion $u,v,w$ by $u,w$ in the shortest path graph. Doing this for each repetition one gets a tour in the shortest path graph having the same length as the original walk. Since the walk was optimal the tour is optimal too.
For the other side, given an optimal tour of the new graph, replace each edge $uv$ of the tour by a shortest weighted path from $u$ to $v$ is the original graph. This walk may contain some repetitions, but has now the same length as the tour, and it is optimal.
-
$\begingroup$ @Florent What about the case where a solver for my problem visits a node twice? Won't that make the solution to my problem inapplicable to TSP? $\endgroup$– DejasCommented Apr 29, 2011 at 18:05
-
-
$\begingroup$ @Dejas, I think what @Florent is saying is that you need to replace the cost of and edge $uv$ with the cost of the minimum path from $u$ to $v$. Then solve Metric TSP on the new graph. $\endgroup$– bbejotCommented Apr 29, 2011 at 18:46
-
1$\begingroup$ Doesn't Metric TSP require that the edges form a metric? If I assign weights 1, 1, 5 to some three edges, it will be cheaper to traverse the short edges rather than take one long edge. $\endgroup$ Commented Apr 29, 2011 at 23:08
-
1$\begingroup$ @John If by 'shortest path' Florent means 'shortest weighted path' then the conversion that Florent describes in the second paragraph would eliminate the weight-5 path. $\endgroup$ Commented Apr 30, 2011 at 7:11