In a 相关主题 https://stackoverflow.com/questions/28333756/finding-most-efficient-path-between-two-nodes-in-an-interval-graph/28333937#28333937，有人建议我实现 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)。我这样做是因为这是迄今为止所看到的最小值。然后将最短路径的值设置为2 as 7。它永远不会再改变这个值，因为任何其他路径1 to 2必须更大（因为它必须从边缘之一开始1-3 (9) or 1-6 (14)).
将已知节点视为单个节点
推断接下来会发生什么的一种方法是假设算法将“已知”节点合并为一个节点。在这个例子中，只要最短路径2被选择，它合并1 and 2作为单个逻辑节点。所有边都出2增加了7（到的最短路径2）。下一步是选择从“超级节点”传出的最小边。那么推理与第一步相同：
6 _ 3
| /
14| /9
|/
1,2-------4
22
在这种状态下，下一个选择的边是1,2-3 (9)。到达的最短路径3被设置为9现在，它的所有边都被考虑选择下一个最小值（请注意如何将边选择为下一个最小值）6 and 4已更新）：
6
|
11|
|
1,2,3----4
20
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
