Shortest total path among set of Latitude/Longitudes

views:

227

answers:

+1 Q:

Shortest total path among set of Latitude/Longitudes

I have a set of 52 or so latitude/longitude pairs. I simply need to find the shortest path through all of them; it doesn't matter where staring point or ending point is.

I've implemented Dijkstra's algorithm by hand multiple times before and don't really have the time to do it again. I've found a couple things that come close, but most require raw graphs with pre-computed weights for each edge.

Do you know of any libraries or existing scripts/applications which will compute the shortest path in this manner? The code/libraries would preferably use Python or Clojure but it really doesn't matter.

Thanks

Isn't this the Traveling Salesman Problem, and therefore there is no efficient way to solve it?

Ned Batchelder 2009-11-01 02:08:19

It's TSP without the stipulation of ending where you started, so you should in theory get a much shorter total distance.

Brian Gianforcaro 2009-11-01 02:12:52

Pish! TSP is O(n!) isn't it? He's only got 52 pairs = something like 8.07e+67 possibilities, no? :p

Mark 2009-11-01 02:17:09

No efficient way to find the _optimal_ solution perhaps... but there are _fairly good_ solutions.

Craig McQueen 2009-11-01 04:05:24

+3 A:

If this is a closed path, it is the Traveling Salesman Problem, and a sub-optimal but quite effective way to resolve it is to use Simulated Annealing

Mathias 2009-11-01 02:12:35

TSP doesn't require a closed path. Without a closed path, the problem is the same, just the metric for the total path length is different. On a closed path, the best path is the one where the `sum of all edges` is minimal. If the path does not has to close, it's the `sum of all edges - the longest edge`

THC4k 2009-11-01 03:10:29

@THC4k I know that wasn't the question at all, but that comment just totally let me finish my code in the easiest simplest way. I already had TSP solved with the closed path. Thanks!

Brian Gianforcaro 2009-11-01 03:30:34

+2 A:

In python, the best graph handling library I was able to put my hands on is networkx. It supports a broad range of different algos for short path search.

Go for it. It's really complete and well designed.

Stefano Borini 2009-11-01 07:43:09

ansaurus

tags:

views:

answers:

Shortest total path among set of Latitude/Longitudes

related questions