boostorg / boostorg/graph

Shortest Path with max distance

Open
#444 3 comments 0 reactions 0 assignees View on GitHub
algorithm
Dominant language
C++
Stars
392
Forks
239
Avg merge
1d 11m
Merged PRs (30d)
20

Description

I am interested in finding the one-to-many shortest path only if it is below a certain max distance D. If a node is farther than D, the distance shall be inf, as usual from a non reachable node. I am considering non negative weights (maybe also just positive).

My focus is mostly performance: I could run the full one-to-many search with Dijkstra and then simply post process the solution. But I expect that the node actually reachable within D are significantly less than the full graph.

Despite being possible to use the RCSP, this seems to me a simple extension of Dijkstra that I wonder it could be achieved in BGL.

My idea is would be to prevent a new node to be inserted in the queue if its distance from the source exceed D. From a quick glance at the BFS visit it does not seems possible to hack on that.

Any suggestion?

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.