Dijkstra的算法具有反向跟踪？
问题内容：
在一个相关的线程中，有人建议我暗含Dijkstra的算法，以找到图形上的最短路径。看一下维基百科算法的.gif文件：
如果路径1,3,6,5成本很低怎么办？例如，3-6的权重为1，6-5的权重为2？Dijkstra的算法不会考虑这条路径，因为它只向前看了一步。它跳过了节点3。
在选择每个节点之前，指定一个使算法看起来比前面快2,3,4 …
n步的参数是否可接受？我意识到这可能会浪费计算时间，但是只要节点不是很密集（即每个节点不超过3或4个连接），这可能会在性能和针对特定数据集的最佳解决方案之间取得不错的平衡。
有人对此有强烈的感觉吗？具有这种可调参数的最短路径算法是否可能出现在图形包中？
问题答案：
Dijkstra算法始终会找到最短路径（在没有负边的图中），并且永远不会回溯。很容易对此进行推理。
始终选择最小值
考虑一个节点及其边缘（它只是大图的一部分）：
6 _ 3
| /
14| /9
|/
1-------2
7
Dijkstra的算法将开始选择边1-2 (7)。我这样做是因为这是到目前为止所看到的最低要求。然后将最短路径的值设置为2as
7。它永远不会再更改此值，因为从1to的任何其他路径都2必须更大（因为它必须以edge1-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更新）：
6
|
11|
|
1,2,3----4
20
