Computer Science On The Hiking Trail
March 2026
I'm not sure what I like more - spending time outside with friends, or solving tricky puzzles. This project was an exciting opportunity to combine the two.
One of my favorite places for hiking is the Dolly Sods Wilderness Area in Monongahela National Forest, West Virginia. It's a beautiful plateau with a huge diversity of ecosystems, many of which are usually only found much farther north. Backcountry camping is allowed almost everywhere in the park, so it's very popular with backpackers. I especially like some of the trails that tunnel through huge growths of mountain laurel, and the wild blueberries that grow on the sides of some trails.
Routefinding
Dolly Sods has a spiderweb of well-marked trails that regularly intersect with each other. There are 46 miles of trail in total, and plenty of popular routes through them that hit the highlights. I've taken trips there a few times, but still haven't seen all of the trails.
I've always wondered what it would take to hike every trail in a single trip. This would require plenty of doubling back, and the optimal route would be very hard to find without the aid of a computer.
This problem was inspired by a college friend who completed the "Metro Challenge" - riding to every station in the DC Metro system in one day. While researching for this blog post, I discovered that a computer science student at my school recently repeated this feat - they published a fantastic podcast about their experience and an accompanying article on Greater Greater Washington
Reviving an Old Project
I actually started this project a long time ago. As a grad student at Virginia Tech, I did an independent study working with a professor who was interested in finding the optimal route to hike The Long Trail Side-to-Side Challenge.That project was far more complex. I learned a lot, but we never got to a very satisfying result. In case anyone is interested, I've linked our final report here. It goes into the math much deeper than I will in this blog post.
I had played around with a map of Dolly Sods at some point in that project, but hadn't saved any of my work.
This year, I'm auditing a discrete math class at my school. It's been a long time since I officially studied discrete math, and I'm planning to take over this class someday, so I thought it would be good to be a student in the class first. We're currently working through our chapter on graph theory (following this wonderful open-source textbook) and just finished doing some exercises about Eulerian circuits. I was reminiscing about this project and decided to go back, brush off the cobwebs, and clean it up to share with my fellow students.
Background - Graph Theory
When most people think about graph theory, the first example that comes to mind is the Travelling Salesperson Problem - where someone needs to find the optimal route to visit a bunch of cities. The input to the problem is a "graph" - a list of places to visit ("nodes") and routes that travel between them ("edges").
The Travelling Salesperson Problem is all about visiting all the nodes. My goal is to visit all of the edges - on a hiking trail system, the nodes are just intersections, which aren't particularly exciting places to visit. This is similar to the famous Seven Bridges of Königsberg Problem - Euler famously invented graph theory in order to solve this problem in the 1700's.
The seven bridges problem asked whether it was possible to take a walk through Königsberg, Prussia that crossed all seven bridges over the river Pregel without crossing the same bridge twice. Euler's famous conclusion was that it was not possible. In modern graph theory, we say that a graph is "Eulerian" if such a tour is possible.
So Euler's solution ends with concluding that the tour is not possible. But what if you're willing to double back? This is yet another famous problem in graph theory called the Chinese Postman Problem (named "Chinese" because it was first proposed by a professor in China. I prefer to just call it the "Postal Routing Problem"). That problem imagines a delivery truck that must drive down every road in a city - much closer to my goal of walking down every hiking trail in a park.
Digitizing The Map
I started with the official trail map from the US Forest Service website. I wrote some Python code that opened the map into an interactive window that could record the coordinates as I clicked on all 36 trail intersections. After that, I wrote a new Python program that loaded the list of nodes, and then I manually added edges between the nodes for each hiking trail. The result was a graph represented in NetworkX format, which I could visualize with Pyplot.
In this graph, I colored the trails red. There are also some state roads that run down the east and south sides of the park, colored in black. I'm not requiring that I walk down those roads as part of this project, but I'm making them available - sometimes they are the only way to get to isolated trails, and sometimes walking on the road will be more efficient than doubling back on a long trail.
Problem Formulation
This problem is too complex to solve with pen and paper. To solve it, I used a math technique called Integer Programming. This is similar to traditional linear programming, which seeks to optimize some objective function subject to constraints, but adds the extra requirement that all of the answers must be integers.
I created two separate variables for each edge in the graph - one for each direction. The value of the variables in the solution will represent how many times I need to walk down that trail. So if the optimal path requires walking north on a trail twice and south on the trail once, the values of the two variables would be 2 and 1, respectively. This is where the "integer" part of the formulation comes in - it wouldn't make sense for me to walk the length of a trail 0.9 times.
The objective function that needs to be minimized is just the sum of all of the values of those variables, multiplied by the length of each trail (so, a solution that requires doubling back on a 1-mile trail is better than a solution that requires doubling back on a 2-mile trail).
Finally, in order to have a complete tour, I added "evenness" constraints - which say that the number of times I take a trail into an intersection needs to be exactly equal to the number of times that I take a trail out of that intersection. We call these values the "in-degree" and "out-degree" of the node, and if they aren't equal, I'd get stuck at the intersection.
Solving
Formulating the problem is the easy part - Integer programming is NP-complete (which, in simple terms, means it's in a list of problems that we know are basically impossible for computers to solve efficiently solve), but there are lots of strategies that find good solutions. I used a tool called Gurobi to calculate the solution - so I just called a pre-written function and got a good result.
The solution to the ILP says that the total mileage would be 63.5. The total mileage of the trails by themselves is 48.5, so the complete tour requires 15 miles of doubling back/walking on roads. But this solution only tells me the length of the route - there is still some work to figure out what the route is.
With the solution from Gurobi, I produced this graph, which shows the number of times each trail needs to be traveled in each direction.
From there, I used some utilities built into NetworkX which convert this graph with the variable solutions into a MultiDiGraph - a graph which includes duplicated trails so that each trail can be crossed once. In the original bridge problem, this final graph is similar to constructing duplicates of existing bridges in order to make the tour possible.
With the solution worked out and the graph built, I created this animation to help me understand the exact route:
Code
For anyone interested in playing with the code and the outputs themselves, I've posted all of my code in a series of well-commented Jupyter Notebooks here: https://github.com/cj0ne5/LongTrailGraph/tree/master/Practice_Problems/dolly_sods.
Hiking, Optimally
Despite years of talking about it, I haven't actually done this trip. If I ever do, I'll be sure to update this post with a trip report. If anyone reads this and wants to join me for a 63.5 mile backpacking trip in West Virginia, please contact me! In the meantime, here are some more photos from past trips out to Dolly Sods.
