Dijkstra 的算法集
Dijkstras Algorithm Sets
我目前正在复习其中一门考试，遇到了这个问题，
"Show, step by step, the use of Dijkstra’s algorithm to find the shortest path from the vertex A to each other vertex in the graph. At each step the known and frontier sets should be clearly indicated."
我知道如何找到最短路径，但我不确定边界集是什么？
谢谢！
制定 Dijkstra 算法的方法有很多种，但大多数版本背后的核心思想是将节点分为三组：
您已经知道从起点开始的最短路径的节点。这最初只是起始节点，并且随着算法运行时间越来越长而增长。
边界节点。这些是与第一组中的节点相邻的节点，您可以猜测到该节点的距离，但不一定能确定猜测是否正确。在算法的每一步中，您都选择边界中成本最低的节点并将其移动到已知最短路径的节点组中。
未探索的节点。这些都是剩下的节点。
如果您使用优先队列实现 Dijkstra 算法，那么前沿节点通常是优先队列中的节点。如果您维护到节点的候选距离列表，而不是在每个点选择最便宜的距离，则边界由候选距离不是无穷大的所有节点组成。
我目前正在复习其中一门考试，遇到了这个问题， "Show, step by step, the use of Dijkstra’s algorithm to find the shortest path from the vertex A to each other vertex in the graph. At each step the known and frontier sets should be clearly indicated." 我知道如何找到最短路径，但我不确定边界集是什么？ 谢谢！
制定 Dijkstra 算法的方法有很多种，但大多数版本背后的核心思想是将节点分为三组：
您已经知道从起点开始的最短路径的节点。这最初只是起始节点，并且随着算法运行时间越来越长而增长。
边界节点。这些是与第一组中的节点相邻的节点，您可以猜测到该节点的距离，但不一定能确定猜测是否正确。在算法的每一步中，您都选择边界中成本最低的节点并将其移动到已知最短路径的节点组中。
未探索的节点。这些都是剩下的节点。
如果您使用优先队列实现 Dijkstra 算法，那么前沿节点通常是优先队列中的节点。如果您维护到节点的候选距离列表，而不是在每个点选择最便宜的距离，则边界由候选距离不是无穷大的所有节点组成。