The Algorithm file for pgr_dijkstra

[ritwikraj1]

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]

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

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 > <#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 <#962 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AYdF5SeM8X-tt1Pd6PVfJ3PHz_sfQ6Qjks5s0y8agaJpZM4QYQ0c> .

[woodbri]

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 ***@***.***> 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 > > <#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 > <#962 (comment)>, > 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 <#962 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AAxJghmPNoS8pimE5LuLfFX3ZN5e92Vjks5s0z1agaJpZM4QYQ0c>.

[cvvergara]

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]

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]

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.