Boost::graph Dijkstra ：最初填充队列
我正在使用 boost::graph 及其 Dijkstra 实现。
我想计算从一组顶点到另一组顶点的最短路径。 我不想计算这些集合之间的所有可能路径。
这个想法如下：我在一栋大楼里，各个街道都有入口。这样我就可以在任何一条街道上开始我的旅程。但我只对最短的感兴趣。
如果我使用自己的 Dijkstra 算法实现，我会执行以下操作：
- 对于每个起始节点，将距离映射到 0
- 将起始节点添加到优先级队列。
虽然使用boost::dijkstra_shortest_paths_no_init很容易将距离图设置为0，但我不知道如何将节点添加到优先级队列中。 我查看了源代码，这似乎几乎是不可能的。 所以我正在考虑定义我自己的组合函子，如果我到达起始节点之一，它将返回 0 距离，但它看起来相当丑陋。
我可以创建一个虚拟节点，并将从虚拟节点的边添加到起始节点。但是，这会引发一些我想避免的并发访问问题。
我是否错过了 boost 库中的可能性，或者是否有人知道一个聪明的解决方法。我还在考虑修补提升以允许优先级队列的自定义初始化。
I'm using boost::graph and its Dijkstra implementation.
I want to compute THE shortest path from a set of vertices to another set of vertices.
I do not want to compute all the possible paths between those sets.
The idea is the following : I'm in a building with entrances on various streets. So I can start my journey on any of those streets. But I'm only interested in the shortest one.
If I had used my own implementation of Dijkstra's algorithm, I would have done the following:
- For each start node, the distance map to 0
- Add the start node to the priority queue.
While it's easy to set the distance map to 0 using boost::dijkstra_shortest_paths_no_init, I cannot figure out how to add the node to the priority queue.
I looked into the source code, and it seems pretty much impossible.
So I'm thinking of defining my own Combine functor that will return a 0 distance if I reach one of the start nodes, but it seems rather ugly.
I could create a virtual node, and add edges from the virtual node to starting nodes. However, this triggers some concurrent access problems I would like to avoid.
Did I miss a possibility in the boost library, or does someone know of a clever workaround. I'm also thinking of patching boost to allow a custom initialization of the priority queue.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
我没有使用过 boost::graph，我希望对其有更深入了解的人会给出更好的答案，但也许您可以创建一个包装现有图表的图表类型，保持原始图表不变，但将其暴露给算法包含虚拟节点和边的视图？如果不是的话，是不是不能复制整个图呢？
I've not used boost::graph, and I hope somebody with better knowledge of it will give a better answer, but perhaps you could create a graph type that wraps the existing graph, leaving the original unmodified, but exposing to the algorithm a view that includes your virtual nodes and edges? If not, is it infeasible to copy the whole graph?