最短路徑演算法

---

---

最短路徑演算法是一種找到從源節點 (S) 到目標節點 (D) 的最低成本路徑的方法。在這裡，我們將討論 Moore 演算法，也稱為廣度優先搜尋演算法。

Moore 演算法

• 標記源頂點 S 並將其標記為 i 並設定 i = 0。

• 找到與標記為 i 的頂點相鄰的所有未標記的頂點。如果沒有任何頂點連線到頂點 S，則頂點 D 未連線到 S。如果存在連線到 S 的頂點，則將其標記為 i+1。

• 如果 D 已標記，則轉到步驟 4，否則轉到步驟 2 以增加 i = i+1。

• 找到最短路徑的長度後停止。

Dijkstra 演算法

Dijkstra 演算法解決了有向加權圖 G = (V, E) 上的單源最短路徑問題，其中所有邊的權重均為非負數（即對於每條邊 (u, v) Є E)，w(u, v) ≥ 0）。

在以下演算法中，我們將使用一個函式 Extract-Min()，它提取具有最小鍵的節點。

演算法：Dijkstra-Algorithm (G, w, s)

for each vertex v Є G.V  
   v.d := ∞ 
   v.∏ := NIL 
s.d := 0 
S := Ф 
Q := G.V 
while Q ≠ Ф 
   u := Extract-Min (Q) 
   S := S U {u} 
   
   for each vertex v Є G.adj[u] 
      if v.d > u.d + w(u, v) 
         v.d := u.d + w(u, v) 
         v.∏ := u

分析

該演算法的複雜度完全取決於 Extract-Min 函式的實現。如果使用線性搜尋實現 Extract-Min 函式，則該演算法的複雜度為 O(V² + E)。

在此演算法中，如果我們使用最小堆，Extract-Min() 函式在該堆上工作以從 Q 返回具有最小鍵的節點，則可以進一步降低該演算法的複雜度。

示例

讓我們考慮頂點 1 和 9 分別作為起點和終點。最初，除起點外的所有頂點均標記為 ∞，起點標記為 0。

因此，頂點 9 與頂點 1 之間的最小距離為 20。路徑為

1 → 3 → 7 → 8 → 6 → 9

此路徑是根據前驅資訊確定的。

Bellman-Ford 演算法

該演算法解決了有向圖 G = (V, E) 的單源最短路徑問題，其中邊權重可能為負數。此外，如果不存在任何負權重迴圈，則可以應用此演算法來查詢最短路徑。

演算法：Bellman-Ford-Algorithm (G, w, s)

for each vertex v Є G.V  
   v.d := ∞ 
   v.∏ := NIL 
s.d := 0 

for i = 1 to |G.V| - 1 
   for each edge (u, v) Є G.E 
      if v.d > u.d + w(u, v) 
         v.d := u.d +w(u, v) 
         v.∏ := u 
for each edge (u, v) Є G.E 
   if v.d > u.d + w(u, v) 
      return FALSE 
return TRUE

分析

第一個 for 迴圈用於初始化，執行 O(V) 次。下一個 for 迴圈在邊上執行 |V - 1| 次，需要 O(E) 次。

因此，Bellman-Ford 演算法在 O(V, E) 時間內執行。

示例

以下示例逐步顯示 Bellman-Ford 演算法的工作原理。該圖具有負邊，但沒有任何負迴圈，因此可以使用此技術解決問題。

在初始化時，除源節點外的所有頂點均標記為 ∞，源節點標記為 0。

在第一步中，所有可從源節點到達的頂點都將更新為最小成本。因此，頂點 a 和 h 會更新。

在下一步中，頂點 a, b, f 和 e 會更新。

遵循相同的邏輯，在此步驟中，頂點 b, f, c 和 g 會更新。

在這裡，頂點 c 和 d 會更新。

因此，頂點 s 和頂點 d 之間的最小距離為 20。

根據前驅資訊，路徑為 s → h → e → g → c → d