131: Traveling Salesman

from MathGIFs:

This is a visualization of the Traveling Salesman problem.

"One of the most famous problems of math and computer science is the Traveling Salesman Problem. Given a list of n cities, what is the shortest tour that visits each city exactly once and returns back to the starting city? One of the reasons why this problem is so famous is that it is easy to understand the problem and incredibly hard to solve the problem. The animation above illustrates the steps a computer algorithm used to arrive at what we think is the shortest distance - 12,930 miles - needed to visit all 48 continental US capitals. (We used Google maps to use actual roads and highways when computing the distances between cities.) The best way to view the animation is to watch only one part of the US at a time, like the northeast. Then you can see how the web of paths works itself out into an efficient route."

Let's simplify things a bit ...

Find the shortest route through the capitals of the six New England states.