能否在带环有向图上使用BGL的dijkstra_shortest_paths算法

问题解答 #

你完全可以使用BGL的dijkstra_shortest_paths接口求解你描述的这类图的最短路径。

你此前对Dijkstra算法的限制存在误解：Dijkstra算法的唯一前置要求是图中所有边的权重为非负数，和图是否有环、是否为有向图没有关联。你之前听说的「带环图无法求解最短路径」，要么是混淆了其他最短路径算法的限制，要么是把「负权环」的特性错用在了所有环上——只有图中存在总权重为负数的环时，绕环会让路径总权重不断变小，才不存在有效最短路径；而你使用的图所有边权都是非负数，就算存在环，绕环只会让总权重增加或者保持不变，完全不会影响最短路径的正常求解。

BGL的dijkstra_shortest_paths实现完全遵循标准Dijkstra算法逻辑，只要你的输入满足边权非负的条件，无论图是有向图还是带有非负权环，都可以正常输出正确的最短路径结果，和官方文档未标注相关限制的情况一致。

内容的提问来源于stack exchange，提问作者HongGyu Kim