Dijkstra 算法 - 从 A 到 B
dijkstra's algorithm - from A to B
我知道什么是迪杰斯特拉算法。而且我知道当用于查找从 A 到所有其他可能节点的所有路径时，它是最佳的。然而，如果你试图找到从 A 到 B 的路径，它是最优的吗？换句话说，应该在搜索从 A 到 B 的路径时使用它，还是有其他更好的算法用于此用例。
编辑：如果我在找到目标节点后恰好中断循环，我认为它不会工作。假设我有这张图 https://i.stack.imgur.com/orp0N.png 并且我正在尝试从 A 到 D。由于该算法是贪婪的，因此它将首先进入 A->B、B->F（死胡同）、B->E， E->D，总权重为9。虽然有更短的路径。最终会在这条路径之后找到。
您不需要找到从 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。
完成
我知道什么是迪杰斯特拉算法。而且我知道当用于查找从 A 到所有其他可能节点的所有路径时，它是最佳的。然而，如果你试图找到从 A 到 B 的路径，它是最优的吗？换句话说，应该在搜索从 A 到 B 的路径时使用它，还是有其他更好的算法用于此用例。
编辑：如果我在找到目标节点后恰好中断循环，我认为它不会工作。假设我有这张图 https://i.stack.imgur.com/orp0N.png 并且我正在尝试从 A 到 D。由于该算法是贪婪的，因此它将首先进入 A->B、B->F（死胡同）、B->E， E->D，总权重为9。虽然有更短的路径。最终会在这条路径之后找到。
您不需要找到从 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。
完成