迪杰斯特拉最短路徑

迪傑斯特拉算法（Dijkstra's algorithm）是一種用於尋找加權圖中單源最短路徑的算法。該算法採用貪心策略，通過不斷標記已訪問的頂點和更新未訪問頂點的最短路徑，最終找到源點到所有其他頂點的最短路徑。

具體步驟如下：

1. 初始化：選擇一個源點，將源點加入已訪問集合，並創建一個距離數組，用於存儲從源點到圖中每個頂點的最短路徑長度。
2. 標記未訪問頂點：遍歷圖中的所有頂點，如果某個頂點未被訪問過，則將其標記為已訪問，並設定其距離為無窮大（表示當前無法到達該頂點）。
3. 更新最短路徑：對於已訪問的每個頂點，找到距離最小的頂點，並更新其相鄰頂點的距離。如果相鄰頂點的距離更小，則更新相鄰頂點的距離。
4. 重複步驟3：重複上述步驟，直到所有頂點都被訪問過。

迪傑斯特拉算法的時間複雜度為O((V+E)logV)，其中V和E分別表示圖中頂點的數量和邊的數量。該算法適用於查找加權圖中單源最短路徑問題，但在處理權重相同的路徑時可能會出現不唯一解的情況。

在實際套用中，迪傑斯特拉算法常用於網路路由、路徑規劃、社交網路分析等領域。