# Chinese postman problem, but criteria = visit each vetex at least once

Chinese postman problem, but where the postman have to visit each vetex at least once.

Is there a name for this problem?

What is the ideal algorithm to solve this problem?

• en.wikipedia.org/wiki/Travelling_salesman_problem – Yuval Filmus Nov 11 '18 at 20:46
• @YuvalFilmus "where the person has to visit each vetex at least once", not exactly once. – Ryan Cameron Nov 11 '18 at 20:54
• TSP allows visiting each vertex as many times as you want. Just use the shortest distance metric on your graph. – Yuval Filmus Nov 11 '18 at 20:56
• @YuvalFilmus How do I use the "shortest distance metric" on my graph? – Ryan Cameron Nov 11 '18 at 21:12
• See my answer below. – Yuval Filmus Nov 11 '18 at 21:13

Let $$G$$ be an edge-weighted graph. Create a new graph $$G'$$ in which the weight of the edge $$(x,y)$$ is the cost of the shortest path between $$x$$ and $$y$$ in $$G$$. The problem you are interested in is the traveling salesman problem (TSP) on $$G'$$.
• Here $(x,y)$ is the name of the edge connecting vertex $x$ to vertex $y$. Its weight should be the cost of the shortest path from $x$ to $y$ in $G$. – Yuval Filmus Nov 11 '18 at 21:19