c++ - Boost::graph Dijkstra:最初填充队列

Question

我正在使用 boost::graph 及其 Dijkstra 实现。

我想计算从一组顶点到另一组顶点的最短路径。我不想计算这些集合之间的所有可能路径。

想法如下:我在一栋大楼里，入口在不同的街道上。这样我就可以在这些街道中的任何一条上开始我的旅程。但我只对最短的感兴趣。

如果我使用自己的 Dijkstra 算法实现，我会执行以下操作:

• 对于每个起始节点，距离映射到0
• 将起始节点加入优先队列。

虽然使用 boost::dijkstra_shortest_paths_no_init 很容易将距离图设置为 0，但我不知道如何将节点添加到优先级队列。我查看了源代码，这似乎是不可能的。所以我正在考虑定义我自己的 Combine 仿函数，如果我到达其中一个起始节点，它将返回 0 距离，但它看起来相当丑陋。

我可以创建一个虚拟节点，并将虚拟节点的边添加到起始节点。但是，这会触发一些我想避免的并发访问问题。

我是否错过了 boost 库中的一个可能性，或者有人知道一个聪明的解决方法。我也在考虑修补 boost 以允许自定义初始化优先级队列。

Answer 1

我没有使用过 boost::graph，我希望对它有更好了解的人会给出更好的答案，但也许你可以创建一个包装现有图的图类型，保持原始图不变，但暴露给该算法包含您的虚拟节点和边缘的 View ？如果不是，复制整个图是不是不可行？