Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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?

like image 456
Jeroen Avatar asked Mar 23 '10 16:03

Jeroen


1 Answers

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.

like image 190
Graviton Avatar answered Oct 23 '22 09:10

Graviton