Dijkstras算法集

Question

我目前正在修改我的一個考試，並且已經涉及這個問題， 「一步一步顯示，使用Dijkstra算法找到從頂點A到其他頂點的最短路徑圖表，每一步都應明確指出已知邊界和邊界。「 我知道如何找到最短路徑，但我確定了邊界集是什麼？ 謝謝！

Answer 1

有很多方法制定Dijkstra算法，但大多數版本的核心理念是將節點分成三組：

1. 節點，你已經知道從起點的最短路徑。這只是初始節點，隨着算法運行時間越來越長而增長。

2. 節點在邊界。這些是與第一組中的節點相鄰的節點，您可以猜測與節點的距離，但不一定能確定猜測是正確的。在算法的每個步驟中，您選擇邊界中成本最低的節點，並將其移動到您知道最短路徑的節點組。

3. 未發現的節點。這些都是剩下的節點。

如果實現Dijkstra的一個優先級隊列算法，那麼前沿節點通常優先級隊列中的人。如果你維護一個到節點的候選距離列表，而是在每個點選擇最便宜的一個，則邊界由候選距離不是無窮大的所有節點組成。