Dijkstras算法集

Question

我目前正在修改我的一个考试，并且已经涉及这个问题， “一步一步显示，使用Dijkstra算法找到从顶点A到其他顶点的最短路径图表，每一步都应明确指出已知边界和边界。“ 我知道如何找到最短路径，但我确定了边界集是什么？ 谢谢！

Answer 1

有很多方法制定Dijkstra算法，但大多数版本的核心理念是将节点分成三组：

1. 节点，你已经知道从起点的最短路径。这只是初始节点，随着算法运行时间越来越长而增长。

2. 节点在边界。这些是与第一组中的节点相邻的节点，您可以猜测与节点的距离，但不一定能确定猜测是正确的。在算法的每个步骤中，您选择边界中成本最低的节点，并将其移动到您知道最短路径的节点组。

3. 未发现的节点。这些都是剩下的节点。

如果实现Dijkstra的一个优先级队列算法，那么前沿节点通常优先级队列中的人。如果你维护一个到节点的候选距离列表，而是在每个点选择最便宜的一个，则边界由候选距离不是无穷大的所有节点组成。