The Traveling Salesman problem asks for a minimum-cost cycle that visits every city exactly once and returns to its starting city. Cities form vertices, routes form edges, and the visit order may vary. Unlike a minimum spanning tree, the solution must be one giant returning cycle. section 5.7 section 8.2
A direct Swift solution builds and evaluates every candidate tour:
- Expect brute force to become impractical as cities increase: the problem is NP-hard and its difficulty grows exceptionally quickly. section 8.2
Five Vermont cities
Evaluating all tours through Rutland, Burlington, White River Junction, Bennington, and Brattleboro produces a shortest cycle of 318 miles: Bennington → Brattleboro → White River Junction → Burlington → Rutland → Bennington.
