Algorithm: shortest path between all points

问题:

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?

回答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.

回答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.

回答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.

回答4:

I think this is what you're looking for, actually:

Floyd Warshall

In computer science, the Floyd–Warshall algorithm (sometimes known as the WFI Algorithm[clarification needed], Roy–Floyd algorithm or just Floyd's algorithm) is a graph analysis algorithm for finding shortest paths in a weighted graph (with positive or negative edge weights). A single execution of the algorithm will find the lengths (summed weights) of the shortest paths between all pairs of vertices though it does not return details of the paths themselves

In the "Path reconstruction" subsection it explains the data structure you'll need to store the "paths" (actually you just store the next node to go to and then trivially reconstruct whichever path is required as needed).