使用Boost Dijkstra算法與指定的最大距離

Question

我喜歡使用升壓轉換器的Dijkstra算法實現來找到一個節點的最短路徑

然而，在我目前的問題，我有一個巨大的圖表，只需要找到最短路徑尋找最短路徑到一定的距離內的節點

我可以實現這一點我自己，但我相信升壓轉換器的實現是比我更有效率，所以我更喜歡使用升壓爲任務

我只是不知道是否有一個告訴boost的dijkstra停止尋找最短路徑，如果節點太遠 - 就像它會在這種情況下顯着加速算法

Answer 1

這是Dijkstra算法的一個非常簡單的修改。當你迭代來自頂點v的輸出邊時，忽略每個邊e，其中e.weight + v.dist > max。