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?

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

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

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.