# 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 Nov 11, 2018 at 20:46
• @YuvalFilmus "where the person has to visit each vetex at least once", not exactly once. Nov 11, 2018 at 20:54
• TSP allows visiting each vertex as many times as you want. Just use the shortest distance metric on your graph. Nov 11, 2018 at 20:56
• @YuvalFilmus How do I use the "shortest distance metric" on my graph? Nov 11, 2018 at 21:12
• See my answer below. Nov 11, 2018 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'$$.

• What is (x,y)? Do you mean I should set all weights to be the same as the smallest weight in the graph? Nov 11, 2018 at 21:17
• 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$. Nov 11, 2018 at 21:19
• Usually the weights will be different for different edges. Nov 11, 2018 at 21:19
• Thank you for the clarification, but how can this help me? What am I supposed to do after that? Nov 11, 2018 at 21:25
• It’s an extremely well-known problem. There’s a lot of information about it out there. Nov 11, 2018 at 21:34