Hello


I am trying to solve a problem involving a cross-country ski trail map. I wish to travel every trail on the map, at least once, but no more than twice (so I can out-and-back on a destination, for example).


I don't believe this is a TSP problem, as TSP seems to be point oriented (ensuring all points on a map are visited in the shortest path possible), whereas I am looking to visit all paths, in the shortest route possible.


Is there an existing algorithm that could be implemented? Am I overthinking it?


I'm not a math major/minor. I get math, at a university level, but it's not my field of study. Please excuse my lack of knowledge! :)


Thanks in advance.



TSP, but for all routes not all points
Look up [Chinese postman problem](http://en.wikipedia.org/wiki/Chinese_postman_problem). This can be done if and only if your graph is connected.  

Assuming you want to start and end at the same point, you look at the vertices of odd degree and find a minimum-cost perfect matching (where the cost is distance in the graph). Each edge of the graph that is on the shortest route between two matched vertices will be traversed twice: after doubling these edges, you have a connected graph where each vertex has even degree, and you take an Eulerian cycle in that graph.


