# Thread: Lowest-cost cycle passing all edges at least once

1. ## Lowest-cost cycle passing all edges at least once

I've been trying to figure out the solution to the following problem for a number of hours now:

"Attached to this post is a weighted graph. Find a cycle (same start and end point) through the graph so that each edge is passed at least once, and so that the weight sum is minimal".

We've recently been learning about Dijkstra's algorithm but I can't see if and how it could be applied here as we have to pass every edge. The solution I've come up with so far is to start from either b or f , and "eliminating" the b-f edge by going back and forth once. By doing so, the rest of the graph is an Euler graph and we can find a cycle that passes each edge exactly once. If my calculations are correct, the weight sum becomes 39. However, what concerns me is that the b-f edge has the highest weight and that there may therefore be a better (systematic?) solution to the problem.

Any ideas greatly appreciated. Thank you.

2. This seems to be quite an NP complete problem, meaning that there is no algorithm that solves the problem in polynomial time. What you might be able to do however is just make a simple searching algorithm that searches through the whole space, starting with the next edge so that the total value of the current path is the smallest. the first answer it finds is then your solution. Starting point is arbitrary as you have to find a cycle.
I doubt any closed form complete fast algorithm exists for this problem, so that might be your best bet.

I think you might be completely right though, and just following the euler cycle with the added 5 from getting back to the starting point is the fastest way to go. This seeing as you have to go back one edge from any of the uneven edged vertices anyway, but instead of b f you go b e a b, which is 4 long instead of 5.

3. Thanks for the help. I had to hand in the assignment but I'll continue looking for a way to prove (or review) the solution.

P.S. Where in Tokyo are you studying? I'm currently on an exchange year there myself.