3

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.

Improve this question
3
  • 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, 2013 at 14:07
  • 1
    Travelling Salesman Problem (TSP) - en.wikipedia.org/wiki/Travelling_salesman_problem
    – Mapperz ♦
    Feb 6, 2013 at 14:47
  • Would be interested in your findings
    – ca0v
    Feb 12, 2013 at 14:35

2 Answers 2

Reset to default
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

Improve this answer
1

Your problem is known as the Traveling Salesman problem where you don't return to the initial place. In pgRouting 2, this can done using the pgr_tsp function which is documented here.

Improve this answer

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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