Support Bounded Multi-Source Shortest Path for faster sparse graphs
Maintainers usually reply within 3 days
Nobody has claimed this yet.
Assessment
- Difficulty
- 5/5
- Estimated time
- Over a week
- Newbie friendliness
- 20/100
Research direction
The issue references an academic paper on a new shortest-path algorithm. Research would start by reading the linked arXiv paper to understand the algorithm, then examining the existing pgRouting codebase for shortest-path implementations (likely in src/). Determine how to integrate a new algorithm, considering PostgreSQL extension constraints and performance testing. 'Done' would be a working implementation with benchmarks against existing methods.
Written by the indexing model from the issue text.
Description
Just raising an issue to see if its worth adding another algorithm that was recently published: Breaking the Sorting Barrier for Directed Single-Source Shortest Paths - https://arxiv.org/pdf/2504.17033
- 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
-
std::fdim drops partial derivative w.r.t second argument in forward and reverse modePossibly taken @ADITYASINGH1206 claimed this today. Open
Difficulty 1/5 Under an hour Newbie friendliness 85/100
vgvassilev/clad#2534 ·
Maintainers usually reply within 1 day
-
Difficulty 2/5 1-3 hours Newbie friendliness 70/100
Maintainers usually reply within 1 day
-
HAP.cpp fixOpen
Difficulty 2/5 1-3 hours Newbie friendliness 68/100
-
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