algorithm - Dijkstra 算法 - 从 A 到 B

Question

我知道什么是迪杰斯特拉算法。而且我知道当用于查找从 A 到所有其他可能节点的所有路径时，它是最佳的。然而，如果你试图找到从 A 到 B 的路径，它是最优的吗？换句话说，应该在搜索从 A 到 B 的路径时使用它，还是针对此用例有其他更好的算法。

编辑:如果我在找到目标节点后恰好中断循环，我认为它不会工作。假设我有这张图 /image/orp0N.png我正在尝试从 A 到 D。因为这个算法是贪婪的，所以它会首先从 A->B、B->F(死胡同)、B->E、E->D 开始，总权重将为 9 .虽然有更短的路径。最终将在这条路径之后找到。

Answer 1

您不需要找到从 A 到所有节点的距离。您只需在将 B 放入最短路径树后退出循环即可。
从性能的角度来看，没有更好的算法。在最坏的情况下，所有从特定节点寻找最短路径的算法都以 O(n^2) 运行。

编辑。然而，如果我们考虑处理图的一些特定特征(例如顶点和边数的比率)，可以获得稍微更好的性能

编辑2。关于您的样本图。以下是步骤:
1. A加入最短路径树(SPT)
2. 更新不在 SPT 中的邻居。距离(B)=3
3. 使用 min.dist 选择顶点。不在 SPT 中。那是 B。将 B 添加到 SPT。
4. 更新不在 SPT 中的邻居。距离(C)=6，距离(E)=5，距离(F)=4
5. 使用 min.dist 选择顶点。不在 SPT 中。那是 F。将 F 添加到 SPT。
6. F没有邻居。
7. 使用 min.dist 选择顶点。不在 SPT 中。那是 E。将 E 添加到 SPT。
8. 更新不在 SPT 中的邻居。距离(D)=9
9. 使用 min.dist 选择顶点。不在 SPT 中。那是 C。将 C 添加到 SPT。
10. 更新不在 SPT 中的邻居。距离(D)=7.
11. 使用 min.dist 选择顶点。不在 SPT 中。那是 D。将 D 添加到 SPT。
完成