Shortest Path Passing All Routes

Question

Is there a shortest path algorithim that calculates the shortest route passing all available roads, ending where you started? This differs from the Travelling salesman problem as you need to pass through all roads between the cities, not just the cities. The traditional shortest path algorithims do not work because they only calculate the shortest distance between 2 points, and don't guarantee passing through all of the roads. Here is a vague map of my problem.

For a solution to be valid, it must pass through every road in between the points labeled.

Answer 1

Construct the line graph of $G$, then solve the Travelling Salesman Problem on the resulting line graph. This yields the optimal solution to your problem, assuming you want to visit every edge in your graph exactly once.

See also the route inspection problem (also known as the Chinese postman problem).

Answer 2

The optimal solution would be to travel every edge of the graph exactly once. If all the vertices of the graph have even degree then the Euler path is the answer.

Otherwise if you allow to traverse each road twice then you can get a 2- approximation factor algorithm.