Dijkstra最短路徑

Dijkstra's algorithm是一種用於查找圖中兩點之間的最短路徑的算法。它是由荷蘭計算機科學家Edsger Dijkstra在1956年提出的。該算法可以用於任何有向圖或無向圖中，並且可以處理weighted和unweighted兩種情況。

Dijkstra's algorithm的工作原理是基於貪心策略，它首先選擇一個起始頂點，然後逐步擴展到其他頂點，直到找到所有頂點之間的最短路徑。該算法使用了一個名為「已處理頂點集」的數據結構來跟蹤已經找到最短路徑的頂點，以及一個名為「鄰近集」的數據結構來存儲當前正在考慮的頂點的最短路徑。

以下是Dijkstra's algorithm的基本步驟：

1. 初始化一個空的已處理頂點集和一個鄰近集。
2. 將起始頂點放入已處理頂點集中，並將它與圖中所有其他頂點的距離放入鄰近集中。
3. 選擇一個尚未在已處理頂點集中，且其鄰近集中的距離最小的頂點，並將它放入已處理頂點集中。
4. 更新該頂點的所有相鄰頂點的鄰近集中的距離，如果新的距離比原來的短，就更新它。
5. 重複步驟3和步驟4，直到所有頂點都被放入已處理頂點集中。

Dijkstra's algorithm的時間複雜度為O((V+E)logV)，其中V是圖中頂點的數量，E是邊數。如果使用斐波那契堆作為優先佇列，則時間複雜度可以最佳化到O(E + V log V)。

在實際套用中，Dijkstra's algorithm被廣泛用於路由選擇、交通規劃、航空調度等領域。