dijkstra算法詳細步驟

dijkstra 算法用於查找加權圖中從源點到所有其他點的最短路徑，步驟如下：初始化頂點集合 v、距離映射 dist 和上一個頂點映射 prev；主循環中選擇距離最小的頂點 u，更新相鄰頂點的距離和上一個頂點；當 v 中所有頂點已處理時，算法結束。

Dijkstra 算法詳細步驟

Dijkstra 算法是一種用於在加權圖中查找從源點到所有其他點的最短路徑的貪婪算法。其步驟如下：

1. 初始化

• 創建一個包含圖中所有頂點的集合 V。
• 創建一個包含起始點到所有其他點的距離的映射 dist，初始值爲無窮大，起始點爲 0。
• 創建一個包含起始點到所有其他點的上一個頂點的映射 prev，初始值均爲 null。

2. 主循環

• 從 V 中選擇一個距離最小的頂點 u。
• 對於所有與 u 相鄰的頂點 v，計算經過 u 到達 v 的距離 new_dist。
• 如果 new_dist 小於 dist[v]，則更新 dist[v] 和 prev[v]。

3. 停止條件

• 當 V 中的所有頂點都已被處理時，算法結束。

算法示例

考慮以下加權圖：

    A(0)   /   /    B(1)  C(2)

登錄後複製

其中數字表示權重。

初始化：

• V = {A, B, C}
• dist = {A: 0, B: ∞, C: ∞}
• prev = {A: null, B: null, C: null}

主循環：

1) 第一次迭代：

• u = A
• 對於 B：new_dist = 0 + 1 = 1
• 對於 C：new_dist = 0 + 2 = 2
• 更新 dist[B] = 1 和 prev[B] = A
• 更新 dist[C] = 2 和 prev[C] = A

2) 第二次迭代：

• u = B
• 對於 C：new_dist = 1 + 2 = 3
• new_dist > dist[C] = 2，因此不更新

輸出結果：

• dist[B] = 1
• dist[C] = 2
• prev[B] = A
• prev[C] = A

以上就是dijkstra算法詳細步驟的詳細內容，更多請關注本站其它相關文章！