It is some cultural holiday where it is usual for the entire extended family to gather for a reunion meal. You happen to have a private bus that fits everyone. You also happen to be a Good Person™ who will not only be holding the meal at your place, but also offered to pick everyone up from their homes.

Your relatives live in different cities all over the country, so you only want to make one round trip. You live in the south-west, your grandparents in the east, your third cousin in the north-west, and so on. If you wanted to travel the least distance while still picking everyone up, would you head to your third cousin's house first? Since they live the nearest, you can pick them up, then head to the nearest person from them. Or maybe you'll start with your grandparents' house? Then on the long travel back, you'll pick everyone else up on the way. Or perhaps something else?

This is the travelling salesman problem – named after what door-to-door salespeople of the recent past would need to consider to both maximise their profits (by visiting all the cities) and minimise their travel distance. Various heuristic (“not the best”) solutions exist, each with their own advantages and disadvantages.

The version of Christofides' algorithm enacted here includes Joris van Rantwijk’s implementation of the blossom algorithm ported to Javascript by Matt Krick.

Not enough memory to generate all permutations processing... processing...

10 cities


Processing Speed



random solutions to try
likelihood to settle for less
Total Distance Time Taken
excludes draw time
Random - -
Greedy - -
Exhaustive - -
2-opt - -
Christofides' - -