4
$\begingroup$

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!)

$\endgroup$
  • 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łtys Apr 29 '11 at 17:15
  • 2
    $\begingroup$ Travelling salesman problem? $\endgroup$ – Pratik Deoghare Apr 29 '11 at 17:31
  • $\begingroup$ @MachineCharmer TSP doesn't allow node revisiting. $\endgroup$ – Dejas Apr 29 '11 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 Beaudrap May 1 '11 at 2:29
15
$\begingroup$

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.

$\endgroup$
  • $\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$ – Dejas Apr 29 '11 at 18:05
  • $\begingroup$ Florent is right $\endgroup$ – N27 Apr 29 '11 at 18:45
  • $\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$ – bbejot Apr 29 '11 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$ – John Moeller Apr 29 '11 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$ – Artem Kaznatcheev Apr 30 '11 at 7:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.