Dijkstra 的反向跟踪算法？

Question

在中，有人建议我使用 Dijkstra 算法来寻找图上的最短路径。从维基百科看这个算法的 .gif：

如果结果证明路径 1,3,6,5 的成本非常低怎么办？比如3-6的权重是1，6-5的权重是2？ Dijkstra 的算法不会考虑这条路径，因为它只向前看一步；它跳过了节点 3。

是否可以指定一个参数，使算法在选择每个节点之前看起来提前 2、3、4...n 步？我意识到这可能会增加计算时间，但只要节点不是很密集（即每个节点不超过 3 或 4 个连接），这就可以在性能和我们特定数据集的最佳解决方案之间提供一个不错的权衡.

有没有人对此有强烈的感受？并且这种参数可调的最短路径算法是否可能在图包中？

Answer 1

它不会跳过节点 3。它会这样做：

从节点1开始，更新到邻居的距离：

d[2] = 7
d[3] = 9
d[6] = 14

选择与源最小距离的下一个未访问节点，在本例中为节点 2 并更新到其邻居的距离：

d[3] = min(d[3], d[2] + c(2, 3))
     = min(9, 7 + 10)
     = 9

d[4] = min(d[4], d[2] + c(2,4))
     = min(inf, 7 + 15)
     = 22

然后它将选择3：更新到它的邻居的距离：

d[6] = min(d[6], d[3] + c(3, 6))
     = min(14, 9 + 1)
     = 10

然后选择下一个距离最小为 d 的未访问节点并执行相同的操作。选择目标节点时停止。

无需按照您的建议进行操作，只要您的边权重为正，该算法就可以正常工作。

Answer 2

Dijkstra 算法总是找到最短路径（在没有负边的图中）并且从不回溯。很容易推理出来。

考虑一个节点及其边（它只是更大图的一部分）：

    6   _ 3
    |  /
  14| /9
    |/
    1-------2
        7

Dijkstra 算法将开始选择边 1-2 (7)。我这样做是因为这是迄今为止看到的最小值。然后它将 2 的最短路径的值设置为 7。它永远不会再次更改此值，因为从 1 到 2 的任何其他路径必须更大（因为它必须从边 1-3 (9) 或 1-6 (14) 之一开始）。

推断接下来会发生什么的一种方法是假装算法将“已知”节点合并为一个节点。在示例中，一旦选择了到 2 的最短路径，它就会将 1 和 2 合并为一个逻辑节点。所有离开 2 的边都增加 7（到 2 的最短路径）。下一步是选择从“超级节点”传出的最小边。那么推理同第一步：

    6   _ 3
    |  /
  14| /9
    |/
   1,2-------4
        22

在此状态下，下一个选择的边是1,2-3 (9)。到 3 的最短路径设置为 9 并且它的所有边现在都被认为是选择下一个最小值（请注意到 6 和 4 的边是如何被更新):

Dijkstra's algorithm with back tracking?