Dijkstra最短路徑算法

Dijkstra 算法是一種用於查找圖中兩點之間最短路徑的算法。它是由荷蘭計算機科學家艾茲赫爾·戴克斯特拉（Edsger Dijkstra）在1956年提出的。Dijkstra 算法可以解決以下問題：

1. 單源最短路徑問題：給定一個圖和圖中的一個節點（稱為源節點），找到從源節點到圖中其他每個節點的最短路徑。
2. 單目標最短路徑問題：給定一個圖和圖中的一個節點（稱為目標節點），找到從圖中每個節點到目標節點的最短路徑。
3. 全圖最短路徑問題：給定一個圖，找到圖中所有節點之間兩兩最短路徑。

Dijkstra 算法的基本思想是維護一個節點集合 S，開始時 S 為空。算法從源節點開始，逐步擴展到圖中其他節點。在擴展過程中，算法維護一個從源節點到 S 中每個節點的最短路徑。當 S 包含圖中所有節點時，算法停止，此時 S 中的每個節點都與源節點有已知的最短路徑。

以下是 Dijkstra 算法的步驟：

1. 初始化：將源節點 V 的距離設定為 0，將圖中其他所有節點的距離設定為無窮大。將源節點 V 加入集合 S。

2. 重複以下步驟直到集合 S 包含圖中所有節點： a. 選擇一個距離尚未確定的節點 u，使得 u 不在 S 中，且 u 到 S 中所有節點的最大距離最小。 b. 將 u 加入 S。 c. 對於 S 中每個與 u 相鄰的節點 v，如果從 u 到 v 的距離加上 v 到 u 的距離小於 v 到源節點的當前已知距離，更新 v 到源節點的距離。

3. 算法結束時，S 中每個節點到源節點的最短路徑距離都已確定。

Dijkstra 算法的時間複雜度為 O(V^2)，其中 V 是圖中節點的數量。如果圖中存在負權邊，Dijkstra 算法將不再適用，因為在這種情況下，最短路徑可能不滿足貪心選擇的原則。此時可以使用貝爾曼-福特算法（Bellman-Ford algorithm）或者弗洛伊德算法（Floyd-Warshall algorithm）來找到最短路徑。

在實際套用中，Dijkstra 算法通常用於找到從一個節點到圖中其他節點的最短路徑，而不是全圖的最短路徑。對於全圖的最短路徑問題，可以使用 Dijkstra 算法多次，每次選擇不同的源節點，或者使用更通用的算法如弗洛伊德算法。