Algorithm - Graph Theory - Lec 3

Sigle Source Shortest Path - Dijkstra Algorithm

Algorithm
Algorithm / Graph Theory / NTU

呈前一講的討論，我們有了個求單源最短路徑的演算法Bellman-Ford (複雜度為 $\mathcal{O}(VE)$ )，現下我們考慮額外的限制條件(邊權重為非負)，想找出是否存在更有效率的演算法

三角不等式

\[ \forall u,v,x \in V, \, \text{we have} \, \delta(u,v) \leq \delta(u,x) + \delta(x,v) \]

其中 $\delta(u,v)$ 表示 $u, v$ 間的最短距離。\
此為 Dijkstra 所根據的直觀原理，也是其為何不能處理負邊問題的原因(只有正邊時顯然成立)。

之前討論在 Bellman-Ford 中的一些觀察討論到 relax 邊的順序，決定了演算法運行的時間。而根據上方的論述，我們可以找到一個最優的訪問邊之順序。簡單來說，我們將節點分為兩個集合，一個集合表示最短路已被設好的節點，另一個表示還未確定者，而每一次都從還未確定者中，選出當前 d 值最小的節點來做 relax。

根據三角不等式，這樣的 Greedy 策略是沒有問題的，因我們選出的節點 $v$ ，所對應的 d[$v$] 已經不可能再更動了 (無法找到經由其他點的路徑使得距離成本 $<$ d[$v$])。

Psuedo Code

其實跟 Bellman-Ford 非常相像。

# Init
for v in G(V):
  d[v] = ∞ 
  π[v] = NULL
d[s] = 0

Pick u which d[u] is MIN
remove u
for v in adj[u]:
  relax(u,v)

Complexity Analysis

通常以 heap 來實做，但效率如何則取決於我們使用何種 heap。需要

  1. $\mathcal{\Theta}(V)$ INS
  2. $\mathcal{\Theta}(V)$ Extract-Min
  3. $\mathcal{\Theta}(E)$ Decrease(v,*)

若用 binary heap 的話，複雜度為 $\mathcal{\Theta}(E \log E + V\ log V) = \mathcal{\Theta}((E+V) \log V)$ \
若用 Fibonacci heap 的話，均攤複雜度為 $\mathcal{\Theta}(E + V \log V)$

Implementation

在 C++ 中以 priority_queue 來實做 heap。 在 Relax 時，會希望用 Decrease，而非 insert 一個新的 vertex 進去之因，是為了不希望 priority_queue 中有太多元素(別忘了 ExtractMin，也就是 pop() 需要成本)，但實做上因為不能透由 iterator 去 traverse 看 queue 中 是否已經存在該 vertex ，還是得把可能已經在 queue 中的 vertex 給放進去…

但如果不管該 vertex 是否已 pop 出來，還繼續去檢查它的每個邊，看是否可以 Relax (透由上方的討論，我們知道這不可能)的話，就是浪費了。如此 queue 中至多 $\mathcal{\Theta}(E)$ 個元素，每 pop 出一個 vertex ，至多要做 $\mathcal{\Theta}(V)$ 次檢查是否可以 Relax 的判斷 (最差就完全圖的情況)，所以複雜度 total 為 $\mathcal{\Theta}(E \log E + EV )$。但如果我們注意到這件事，不再去對已經 pop 過的邊做 Relax 與否的檢查，那麼複雜度則會降為 $\mathcal{\Theta}(E \log E + V^2)$ ，而這也是下方 code 中， b_set 的功能。 ( $\mathcal{\rightarrow}$ 練習，如果你 running time 超過 0.3 秒的話，大概就是寫成 $\mathcal{O}(EV)$ 了😅)。

Reference

 
comments powered by Disqus