Algorithm: shortest path between all points

Question

Suppose I have 10 points. I know the distance between each point.

I need to find the shortest possible route passing through all points.

I have tried a couple of algorithms (Dijkstra, Floyd Warshall,...) and they all give me the shortest path between start and end, but they don't make a route with all points on it.

Permutations work fine, but they are too resource-expensive.

What algorithms can you advise me to look into for this problem? Or is there a documented way to do this with the above-mentioned algorithms?

Solution 1

Have a look at travelling salesman problem.

You may want to look into some of the heuristic solutions. They may not be able to give you 100% exact results, but often they can come up with good enough solutions (2 to 3 % away from optimal solutions) in a reasonable amount of time.

Solution 2

This is obviously Travelling Salesman problem. Specifically for N=10, you can either try the O(N!) naive algorithm, or using Dynamic Programming, you can reduce this to O(n^2 2^n), by trading space.

Beyond that, since this is an NP-hard problem, you can only hope for an approximation or heuristic, given the usual caveats.

Solution 3

As others have mentioned, this is an instance of the TSP. I think Concord, developed at Georgia Tech is the current state-of-the-art solver. It can handle upwards of 10,000 points within a few seconds. It also has an API that's easy to work with.