search

pgRouting / pgrouting

Repository contains pgRouting library. Development branch is "develop", stable branch is "master"
https://pgrouting.org
GNU General Public License v2.0
1.17k stars 369 forks source link

The Algorithm file for pgr_dijkstra #962

Open ritwikraj1 opened 7 years ago

ritwikraj1 commented 7 years ago

Hello Everyone,

I am trying to implement the time-dependent version of Dijkstra's Algorithm, and for that I was looking for the pgr_dijkstra implementation in PGRouting source code files. But I have been unable to find it. Could anyone help me out with it?

I tried implementing Dijkstra's algorithm in Python, but it takes around 40 seconds to find the shortest path for a graph with 38000 nodes. And it gives the result instantaneously using pgr_dijkstra for the same graph. I am struggling to understand how pgr_dijkstra runs so fast. Is it using some sort of approximate solution, or it gives the optimal solution? Any help would be much appreciated.

Thank you, Ritwik

woodbri commented 7 years ago

pgRouting uses the Boost Graph code in the solver. So the basic workflow inside pgRouting is:

  1. get edges from the database
  2. build a Boost graph from the edges
  3. solve the graph using Boost
  4. return the results back to the database

Boost is fast and reliable C++ algorithms. So you would want to look into Boost Graph as there are a lot of hooks into the solver that let you inject your own code into the solver. Looks for visitor hooks.

-Steve

On 11/9/2017 11:41 AM, ritwikraj1 wrote:

Hello Everyone,

I am trying to implement the time-dependent version of Dijkstra's Algorithm, and for that I was looking for the pgr_dijkstra implementation in PGRouting source code files. But I have been unable to find it. Could anyone help me out with it?

I tried implementing Dijkstra's algorithm in Python, but it takes around 40 seconds to find the shortest path for a graph with 38000 nodes. And it gives the result instantaneously using pgr_dijkstra for the same graph. I am struggling to understand how pgr_dijkstra runs so fast. Is it using some sort of approximate solution, or it gives the optimal solution? Any help would be much appreciated.

Thank you, Ritwik

— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub https://github.com/pgRouting/pgrouting/issues/962, or mute the thread https://github.com/notifications/unsubscribe-auth/AAxJgoOqPNIiZxZisX2qgRgFd9NVjVArks5s0ytAgaJpZM4QYQ0c.

This email has been checked for viruses by Avast antivirus software. https://www.avast.com/antivirus

ritwikraj1 commented 7 years ago

Hello Steve,

Thank you so much for your reply. Do you know if the solution provided by Boost is exact or approximate? Are they using the pure Dijkstra algprithm, or some variation of it to get a heuristic solution? Also, it would be great if you could direct me to the Boost C++ algorithm file for Dijkstra. Thank you again.

-Ritwik

On 9 November 2017 at 11:58, Stephen Woodbridge notifications@github.com wrote:

pgRouting uses the Boost Graph code in the solver. So the basic workflow inside pgRouting is:

  1. get edges from the database
  2. build a Boost graph from the edges
  3. solve the graph using Boost
  4. return the results back to the database

Boost is fast and reliable C++ algorithms. So you would want to look into Boost Graph as there are a lot of hooks into the solver that let you inject your own code into the solver. Looks for visitor hooks.

-Steve

On 11/9/2017 11:41 AM, ritwikraj1 wrote:

Hello Everyone,

I am trying to implement the time-dependent version of Dijkstra's Algorithm, and for that I was looking for the pgr_dijkstra implementation in PGRouting source code files. But I have been unable to find it. Could anyone help me out with it?

I tried implementing Dijkstra's algorithm in Python, but it takes around 40 seconds to find the shortest path for a graph with 38000 nodes. And it gives the result instantaneously using pgr_dijkstra for the same graph. I am struggling to understand how pgr_dijkstra runs so fast. Is it using some sort of approximate solution, or it gives the optimal solution? Any help would be much appreciated.

Thank you, Ritwik

— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub https://github.com/pgRouting/pgrouting/issues/962, or mute the thread https://github.com/notifications/unsubscribe-auth/ AAxJgoOqPNIiZxZisX2qgRgFd9NVjVArks5s0ytAgaJpZM4QYQ0c.

This email has been checked for viruses by Avast antivirus software. https://www.avast.com/antivirus

— You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub https://github.com/pgRouting/pgrouting/issues/962#issuecomment-343219704, or mute the thread https://github.com/notifications/unsubscribe-auth/AYdF5SeM8X-tt1Pd6PVfJ3PHz_sfQ6Qjks5s0y8agaJpZM4QYQ0c .

woodbri commented 7 years ago

Boost is doing Dijkstra solution. A* Search, Bidirectional, etc are all variants on Dijkstra. All of these are exact solutions.

look at the files here:

https://github.com/pgRouting/pgrouting/tree/develop/src/dijkstra https://github.com/pgRouting/pgrouting/blob/develop/include/dijkstra/pgr_dijkstra.hpp

-Steve

On 11/9/2017 12:58 PM, ritwikraj1 wrote:

Hello Steve,

Thank you so much for your reply. Do you know if the solution provided by Boost is exact or approximate? Are they using the pure Dijkstra algprithm, or some variation of it to get a heuristic solution? Also, it would be great if you could direct me to the Boost C++ algorithm file for Dijkstra. Thank you again.

-Ritwik

On 9 November 2017 at 11:58, Stephen Woodbridge notifications@github.com wrote:

pgRouting uses the Boost Graph code in the solver. So the basic workflow inside pgRouting is:

  1. get edges from the database
  2. build a Boost graph from the edges
  3. solve the graph using Boost
  4. return the results back to the database

Boost is fast and reliable C++ algorithms. So you would want to look into Boost Graph as there are a lot of hooks into the solver that let you inject your own code into the solver. Looks for visitor hooks.

-Steve

On 11/9/2017 11:41 AM, ritwikraj1 wrote:

Hello Everyone,

I am trying to implement the time-dependent version of Dijkstra's Algorithm, and for that I was looking for the pgr_dijkstra implementation in PGRouting source code files. But I have been unable to find it. Could anyone help me out with it?

I tried implementing Dijkstra's algorithm in Python, but it takes around 40 seconds to find the shortest path for a graph with 38000 nodes. And it gives the result instantaneously using pgr_dijkstra for the same graph. I am struggling to understand how pgr_dijkstra runs so fast. Is it using some sort of approximate solution, or it gives the optimal solution? Any help would be much appreciated.

Thank you, Ritwik

— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub https://github.com/pgRouting/pgrouting/issues/962, or mute the thread https://github.com/notifications/unsubscribe-auth/ AAxJgoOqPNIiZxZisX2qgRgFd9NVjVArks5s0ytAgaJpZM4QYQ0c.

This email has been checked for viruses by Avast antivirus software. https://www.avast.com/antivirus

— You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub

https://github.com/pgRouting/pgrouting/issues/962#issuecomment-343219704, or mute the thread

https://github.com/notifications/unsubscribe-auth/AYdF5SeM8X-tt1Pd6PVfJ3PHz_sfQ6Qjks5s0y8agaJpZM4QYQ0c .

— You are receiving this because you commented. Reply to this email directly, view it on GitHub https://github.com/pgRouting/pgrouting/issues/962#issuecomment-343238204, or mute the thread https://github.com/notifications/unsubscribe-auth/AAxJghmPNoS8pimE5LuLfFX3ZN5e92Vjks5s0z1agaJpZM4QYQ0c.

cvvergara commented 7 years ago

A* solution depends on the heuristic used http://docs.pgrouting.org/2.5/en/pgr_aStar.html#description-of-the-parameters-of-the-signatures

0: h(v) = 0 (Use this value to compare with pgr_dijkstra)
dkastl commented 7 years ago

Time-dependent shortest path has been implemented as a GSoC project several years before. It was not added to pgRouting that time, so now it won't be easy to merge. This is the relevant tag in the repository: https://github.com/pgRouting/pgrouting/tree/gsoc/tdsp-lw

It would be very nice to find a sponsor or contributor for such an algorithm. I haven't seen any implementation elsewhere.

MaazouzMehdi commented 2 years ago

Are there news about a time dependent version of Dijkstra ( or other algorithm ) ? Cause I added GTFS data into PostgreSQL database and tried to apply pgRouting algorithms on that data. But my results were biased due to the fact costs are static and not dynamic.