Shortest Path with max distance
- 主要语言
- C++
- 星标
- 392
- 派生
- 239
- 平均合并
- 1 天 11 分钟
- 30 天内合并 PR
- 20
描述
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?
贡献指南
评估
这个 Issue 还没有评估数据。