# How to find the best route through multiple points?

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.

-
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
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

## 2 Answers

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

-

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.

-