0
$\begingroup$

I would like to travel to each edge of the weighted graph at least once choosing the shortest path, i know this problem is similar to the Chinese Postman Problem CPP, but the difference here is that the Start Node is the same Ending Node, it's like an Eulerian circuit but we can travel to the same edge more than once if we need too.

I don't need the exact path but the Value of the Shortest Path

The number of nodes N can be 1 <= N <= 20 The number of Edges M can be 1 <= M <= 100 The weight of the Edges W can be 1 <= W <= 100

$\endgroup$
2
  • $\begingroup$ Welcome to Mathematics SE. Take a tour. You'll find that simple "Here's the statement of my question, solve it for me" posts will be poorly received. What is better is for you to add context (with an edit): What you understand about the problem, what you've tried so far, etc.; something both to show you are part of the learning experience and to help us guide you to the appropriate help. You can consult this link for further guidance. $\endgroup$
    – Another User
    Commented Feb 6 at 19:09
  • $\begingroup$ add a dummy vertex linked to your start node and end node with edges of weight zero, and you are reduced to the chinese postman problem $\endgroup$
    – caduk
    Commented Feb 7 at 13:46

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .