Going through all edges of a graph with minimum cost

Question

I have an undirected graph with weighted edges (each edge with a different possitive weight) and I need to know a way to travel through all edges with the minimum cost, starting in a vertex and ending in the same vertex. So it's kind of similar to the Travelling Salesman Problem but, instead of travelling through all the vertexes and returning to the original vertex, now it is compulsory to visit all edges (and you can travel more than once through every of them but remember that we are minimizing the cost). In summary, I start in a vertex and have to traverse all edges (they have weight) and finally end up in the same vertex where I started with the minimum cost. Can any of the popular algorithms for minimizing costs (Dijkstra, MST...) help me here or I just have to do it by hand (which would be really difficult)??? I applied the Dijkstra algorithm but I don't see how it can help me (ok, i can know the minimum cost to every vertex from the original but that's not helping me right now). Thanks for the help.

Answer 1

If all vertices had even degree, we could do this with an Eulerian tour, which traverses every edge exactly once.

In general, we will not be able to do this, because some vertices have odd degree, causing us to double back on some edges. To figure out how to do this optimally, construct an auxiliary graph $H$ such that:

• the vertices of $H$ are the odd vertices of the original graph.
• between every two vertices, there is an edge whose cost is the total cost of a cheapest path between those vertices in the original graph.

We find a minimum weight perfect matching in $H$, for instance with the blossom algorithm. Then for every pair of vertices paired by this perfect matching, we double the edges on a cheapest path between them in the original graph.

This makes all vertex degrees even, so now an Eulerian tour exists, and this tour is the final answer.