Shortest Path Passing All Routes 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.
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).