1
$\begingroup$

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?

$\endgroup$
5
  • $\begingroup$ en.wikipedia.org/wiki/Travelling_salesman_problem $\endgroup$ Nov 11, 2018 at 20:46
  • $\begingroup$ @YuvalFilmus "where the person has to visit each vetex at least once", not exactly once. $\endgroup$ Nov 11, 2018 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$ Nov 11, 2018 at 20:56
  • $\begingroup$ @YuvalFilmus How do I use the "shortest distance metric" on my graph? $\endgroup$ Nov 11, 2018 at 21:12
  • $\begingroup$ See my answer below. $\endgroup$ Nov 11, 2018 at 21:13

1 Answer 1

1
$\begingroup$

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'$.

$\endgroup$
5
  • $\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$ Nov 11, 2018 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$ Nov 11, 2018 at 21:19
  • $\begingroup$ Usually the weights will be different for different edges. $\endgroup$ Nov 11, 2018 at 21:19
  • $\begingroup$ Thank you for the clarification, but how can this help me? What am I supposed to do after that? $\endgroup$ Nov 11, 2018 at 21:25
  • $\begingroup$ It’s an extremely well-known problem. There’s a lot of information about it out there. $\endgroup$ Nov 11, 2018 at 21:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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