我正在使用boost::graph它的 Dijkstra 实现。
我想计算从一组顶点到另一组顶点的最短路径。我不想计算这些集合之间的所有可能路径。
这个想法如下：我在一座建筑物中，各个街道都有入口。所以我可以在任何一条街道上开始我的旅程。但我只对最短的一个感兴趣。
如果我使用自己的 Dijkstra 算法实现，我会执行以下操作：
- 对于每个起始节点，距离映射为 0
- 将起始节点添加到优先级队列中。
虽然使用 将距离图设置为 0 很容易boost::dijkstra_shortest_paths_no_init，但我无法弄清楚如何将节点添加到优先级队列中。我查看了源代码，这似乎几乎是不可能的。所以我正在考虑定义我自己的组合函子，如果我到达一个起始节点，它将返回 0 距离，但它看起来相当难看。
我可以创建一个虚拟节点，并将虚拟节点的边添加到起始节点。但是，这会触发一些我想避免的并发访问问题。
我是否错过了 boost 库中的一个可能性，或者有人知道一个聪明的解决方法。我也在考虑修补 boost 以允许对优先级队列进行自定义初始化。