2

我喜欢使用 boost 的 dijkstra 实现来找到节点的最短路径

但是，在我当前的问题中，我有一个巨大的图表，只需要找到到一定距离内的节点的最短路径

我可以自己实现这个，但我相信 boost 的实现比我的效率高得多，所以我更喜欢使用 boost 来完成任务

我只是想知道如果节点太远，是否有办法告诉boost的dijkstra停止寻找最短路径——因为在这种情况下它会显着加速算法

4

1 回答 1

2

这是对 Dijkstra 算法的一个非常简单的修改。当您从顶点 v 迭代出边时，只需忽略每个边 e，其中e.weight + v.dist > max.

于 2016-01-14T20:11:43.377 回答