algorithm - Dijkstra 的算法集

Question

我目前正在复习我的一项考试并且遇到了这个问题，“逐步显示使用 Dijkstra 算法找到从顶点 A 到图中每个其他顶点的最短路径。在每一步中，都应清楚地指出已知集和边界集。”我知道如何找到最短路径，但我不确定边界集是什么？谢谢!

Answer 1

Dijkstra 算法有多种表述方式，但大多数版本背后的核心思想是将节点分为三组:

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

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

3. 未探索的节点。这些是所有剩余的节点。

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