boostorg / boostorg/graph

Shortest Path with max distance

未关闭
#444 3 条评论 0 个 reaction 已指派 0 人 在 GitHub 查看
algorithm
主要语言
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 还没有评估数据。

把新 issue 发到你的邮箱

精选适合新手参与的 GitHub issue 摘要。