The Algorithm file for pgr_dijkstra
Maintainers usually reply within 3 days
Nobody has claimed this yet.
Assessment
- Difficulty
- 3/5
- Estimated time
- 1-2 days
- Newbie friendliness
- 45/100
Research direction
The issue asks for the location of the pgr_dijkstra algorithm implementation and an explanation of its performance. Start by exploring the pgRouting source code, likely in the src/ directory, for files related to dijkstra. Look for C++ source files and documentation. Understanding the algorithm's speed requires reading the code and possibly the project's documentation on performance optimizations. Check if there are existing tests or benchmarks that illustrate its behavior.
Written by the indexing model from the issue text.
Description
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
- Dominant language
- C++
- Stars
- 1.4k
- Forks
- 397
- Avg merge
- 2d 16h
- Merged PRs (30d)
- 8
Getting set up
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
More from pgRouting/pgrouting
-
Difficulty 2/5 1-3 hours Newbie friendliness 72/100
Maintainers usually reply within 3 days
-
Difficulty 2/5 1-3 hours Newbie friendliness 82/100
Maintainers usually reply within 3 days
-
Administrative Enhancement
Difficulty 1/5 Under an hour Newbie friendliness 80/100
Maintainers usually reply within 3 days
-
points_input Developers docPossibly taken @withaman69 claimed this 101 days ago. OpenC/C++ Developers Doc. good first issue
Difficulty 2/5 1-3 hours Newbie friendliness 70/100
pgRouting/pgrouting#973 · 10 comments ·
Maintainers usually reply within 3 days
-
get_check_data developers docPossibly taken @withaman69 claimed this 102 days ago. OpenC/C++ Developers Doc. good first issue
Difficulty 2/5 1-3 hours Newbie friendliness 70/100
pgRouting/pgrouting#972 · 7 comments ·
Maintainers usually reply within 3 days
All issues in pgRouting/pgrouting
Similar issues
-
Difficulty 2/5 1-3 hours Newbie friendliness 70/100
Maintainers usually reply within 1 day
-
Difficulty 2/5 1-3 hours Newbie friendliness 70/100
KLayout/klayout#2554 · 1 comment ·
Maintainers usually reply within 1 day
-
Difficulty 2/5 1-3 hours Newbie friendliness 72/100
Maintainers usually reply within 1 day
-
Difficulty 2/5 1-3 hours Newbie friendliness 65/100
LaneDibello/Kotor-Patch-Manager#375 ·
Maintainers usually reply within 2 days
-
Difficulty 2/5 1-3 hours Newbie friendliness 65/100
Maintainers usually reply within 1 day