MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top


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.

share|cite|improve this question
up vote 4 down vote accepted

Look up 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.

share|cite|improve this answer

Pick a spanning tree of the ski trail map, e.g. by depth-first search or something. You can traverse it by always turning left at a junction. As you're doing this, walk out and back along each edge that's not in the tree. This uses each edge exactly twice.

share|cite|improve this answer
But the OP is looking for the shortest route possible, so the hope is to traverse some of the edges only once, and indeed to maximize the total length of the edges that are traversed only once. – Andreas Blass Mar 17 '13 at 20:02

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.