python - Dijkstra 的反向跟踪算法？

Question

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

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

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

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

Answer 1

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 的最短路径)。下一步是选择从“ super 节点”传出的最小边。那么推理同第一步:

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

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

    6
    |
  11|
    |
   1,2,3----4
         20