Take the 2-minute tour ×
Geographic Information Systems Stack Exchange is a question and answer site for cartographers, geographers and GIS professionals. It's 100% free, no registration required.

I am using postgreSQL, postGIS and pgrouting. Now I am really confused on how am I going to find the shortest path between multiple points.

I know how to find it between two points through dijkstra but I am confused how to accomplish the same result with more than two points.

I have done some research and found this: https://github.com/pgRouting/pgrouting/wiki/One_to_many-Dijkstra---To-review

But still I did not understand if its the right way and how to install it.

share|improve this question
    
A shortest path is between two points by definition so you might want to route to point a, then point b, then point c. Alternately you could select all possible routes and then filter for those those routes containing points you are seeking. –  lewis Feb 6 '13 at 14:07
1  
Travelling Salesman Problem (TSP) - en.wikipedia.org/wiki/Travelling_salesman_problem –  Mapperz Feb 6 '13 at 14:47
    
Would be interested in your findings –  ca0v Feb 12 '13 at 14:35
add comment

1 Answer 1

The function you referred may deliver a distance matrix between points, but does not find the shortest path to visit all points. That's indeed the NP-hard Travelling Salesman Problem. Selecting all possible routes is a bad strategy as the number of possible routes will grow exponential with the number of points, e.g. for visiting n locations there are n! routes.

You'd better check this page: http://pgrouting.org/docs/1.x/tsp.html

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.