<p>The TSP problem, given a graph and an edge-weight function, asks to find a tour visiting each vertex exactly once having minimum length.</p>

<p>I think your problem is equivalent to the <a href="http://en.wikipedia.org/wiki/Travelling_salesman_problem#Metric_TSP">Metric TSP problem</a>, 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.</p>

<p>Indeed, a minimum walk on your original graph corresponds to a minimum tour in the newly defined clique, and vice-versa.</p>

<p>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.</p>

<p>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. </p>

CC BY-SA 3.0
2011-04-29T18:05:27.290Z
@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?
Dejas
CC BY-SA 3.0
2011-04-29T18:45:53.683Z
Florent is right
N27
CC BY-SA 3.0
2011-04-29T18:46:13.207Z
@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.
bbejot
CC BY-SA 3.0
2011-04-29T19:57:52.690Z
see here for example, in the introduction: http://math.mit.edu/~goemans/PAPERS/atsp-soda10.pdf
N27
CC BY-SA 3.0
2011-04-29T22:40:19.273Z
the point is that if the solver visits a node twice, then it is not producing an optimal path, and the given path can easily be made shorter by NOT visiting twice. This is a consequence of the triangle inequality.
Suresh Venkat
CC BY-SA 3.0
2011-04-29T23:08:07.023Z
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.
Josephine Moeller
CC BY-SA 3.0
2011-04-30T07:11:50.470Z
@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.
Artem Kaznatcheev
CC BY-SA 3.0
2011-04-30T14:45:25.707Z
I never understood why this happens, by the way. If you take the shortest path weight between any 2 nodes and set an edge between them and you ask to visit each vertex exactly once, then you may lose the property of "visiting each edge exactly once" since by taking the "shortest paths" you visit intermediate vertices that you may have to visit again. Anyway...
N27
CC BY-SA 3.0
2011-05-01T11:17:07.767Z
@N27: You are right, but to my understanding it is not required to visit each edge here.
Florent Foucaud
CC BY-SA 3.0
2011-05-01T11:44:37.780Z
@Artem: I edited "shortest path" to "path of minimum weight".
@Dejas: I edited my answer by adding the correspondance between the walk and the tour. I hope it is clear now.
Florent Foucaud
CC BY-SA 3.0
2011-05-02T09:40:25.940Z
I meant "each node once". sorry
N27
CC BY-SA 3.0
2011-05-03T14:21:44.300Z
@Dejas: if you find the answer satisfactory, please accept it. Otherwise, explain why.
Florent Foucaud
CC BY-SA 3.0
2011-04-29T17:29:04.507Z
2011-05-01T11:42:54.113Z
2011-05-01T11:42:54.113Z
Florent Foucaud
<p>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!)</p>

CC BY-SA 3.0
2011-04-29T17:15:19.113Z
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).
Karolina Sołtys
CC BY-SA 3.0
2011-04-29T17:31:43.367Z
Travelling salesman problem?
Pratik Deoghare
CC BY-SA 3.0
2011-04-29T18:03:29.413Z
@MachineCharmer TSP doesn't allow node revisiting.
Dejas
CC BY-SA 3.0
2011-05-01T02:29:19.257Z
a minor terminological note --- a 'path' which can revisit nodes (or edges) is called a **walk**; "paths" are usually defined to exclude revisiting nodes.
Niel de Beaudrap
<ds.algorithms><graph-theory><graph-algorithms><terminology>
Does this graph problem have a formal name?
Dejas
# Does this graph problem have a formal name?

(Asked by: username_0 on 2011-04-29)

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

**Tags:** ds.algorithms, graph-theory, graph-algorithms, terminology

> **Comments:**
> **username_1**: 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).  
> **username_2**: Travelling salesman problem?  
> **username_0**: @MachineCharmer TSP doesn't allow node revisiting.  
> **username_3**: a minor terminological note --- a 'path' which can revisit nodes (or edges) is called a **walk**; "paths" are usually defined to exclude revisiting nodes.  

---

## 1 answers

### Answer by username_4 on 2011-04-29. Score: 16

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](http://en.wikipedia.org/wiki/Travelling_salesman_problem#Metric_TSP), 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.

> **Comments:**
> **username_0**: @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?  
> **username_5**: Florent is right  
> **username_6**: @username_0, 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.  
> **username_5**: see here for example, in the introduction: http://math.mit.edu/~goemans/PAPERS/atsp-soda10.pdf  
> **username_7**: the point is that if the solver visits a node twice, then it is not producing an optimal path, and the given path can easily be made shorter by NOT visiting twice. This is a consequence of the triangle inequality.  
> **username_8**: 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.  
> **username_9**: @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.  
> **username_5**: I never understood why this happens, by the way. If you take the shortest path weight between any 2 nodes and set an edge between them and you ask to visit each vertex exactly once, then you may lose the property of "visiting each edge exactly once" since by taking the "shortest paths" you visit intermediate vertices that you may have to visit again. Anyway...  
> **username_4**: @username_5: You are right, but to my understanding it is not required to visit each edge here.  
> **username_4**: @Artem: I edited "shortest path" to "path of minimum weight". @username_0: I edited my answer by adding the correspondance between the walk and the tour. I hope it is clear now.  
> **username_5**: I meant "each node once". sorry  
> **username_4**: @username_0: if you find the answer satisfactory, please accept it. Otherwise, explain why.  

---

