dijkstra - Dijkstra 会不会有循环的路径？

Question

注意：没有负成本。

我正在考虑在使用 Dijkstra 的路由中实现掉头。Dijkstra 会推荐 ABCBD 路线而不是 ABD 路线吗？第一次遇到B时，B在访问邻居后被标记为已访问，因此永远不会考虑从BCB循环

在那种情况下，Dijkstra 从不推荐结果中的循环？

Answer 1

TL;DR - 除非循环上每条边的成本为 0，否则这是不可能的。否则，将循环包含在最短路径中会给最短路径增加不必要的成本（这意味着它将不再是最短路径）。

背景：

Dijkstra 通过维护两组顶点进行操作。一组是已经标记的顶点，另一组是尚未标记的顶点。给定这两个集合，Dijkstra 的算法寻找下一个最便宜的元素添加到标记顶点列表中，然后更新到未标记顶点的最短路径。

在 ABC 已被标记且添加的下一条边是 C->B 的情况下，将到达 B 两次，并且从 A 到 B 的成本包括循环是 [x + p + q]。但是，没有循环从 A 到 B 的成本显然是 [x]。现在从 A 到 D 有环的最短路径是 [x + p + q + r]，而没有环的最短路径是 [x + r]。如果 p 和 q 都大于 0，我们看到没有循环的路径会更短。

在一般情况下（边的成本为正），永远不会包含循环，因为最短路径将包含返回循环起点的不必要的额外成本。

如果掉头实际上是最短路径：

为了让 Dijkstra 进行必要的掉头，您可以从 C 重新开始算法并搜索到 D 的最短路径（因此在路由时重新计算通知）。另一种解决方案可能是提前修改底层图表。例如，路径 ABCBD 将变为 ABCZD。或者，来自 C->B 的边和来自 B->D 的边都可以被删除并替换为来自 C->D 的单个边。

Answer 2

它的任务是找到最短（成本最低）的路径......

如果边缘权重等于零的边缘权重大于零，则不会出现循环，这可能会发生，但在您的情况下没有任何意义