Algorithm - Graph Theory - Lec 2

圖的一個常見應用場合是想找出某兩點之間的最短(/長)路徑，此時的邊權重又視為兩節點之間的距離。

Shortest Path Problem

Given a graph $G$, a starting vertex $s$ and edge cost $c_e$
Want: Find the path with min. total cost from $s \rightarrow v$ for some $v$

Bellman-Ford Algorithm

優點:

• 可以處理有負邊的圖
• 能偵測負環 ( Negative Cycle )

Relax (鬆弛)

最短路徑演算法中常看到的名詞，先看程式碼

def relax(u,v):
  if d[v] > d[u] + w(u,v):
    d[v] = d[u] + w(u,v) # 當前最短路的 cost
    π[v] = u # back-tracking

簡單來說就是如果遇到 cost 更小的路徑，就更新。
這也建構於最短路徑問題的特性，若從 $s$ 到 $v$ 的最短路徑中經過 $u$ ，那麼可以確定子路徑 $s \rightarrow u$ 亦為其兩點間的最短路。

Psuedo Code

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

# Iterate |V| - 1 times
for i in range(|V| - 1):
  for e(u,v) in E:
    relax(u,v)

複雜度為 $\mathcal{O}(VE)$

一些觀察

• 實際上也不用跑到 $|V| - 1$ 次才停止，在某一回合如果沒有更新，那麼往後的回合也不可能更新了，此時便可以停止。

• 遍歷邊的順序，影響了需要幾回合才能找到最短路，那麼最佳的順序是什麼呢? ($\rightarrow$ see Dijkstra)

Correctness

• 假設圖上沒有負環，the shortest path from $s \rightarrow v$ has $\leq |V|-1$ edges

proof : By contradiction，若用了 $\geq |V|$ 條邊，該路徑必存在 cycle (某些點被重複拜訪)，但負邊不存在，這麼做只是徒增 cost ( 故可把 cycle 拔掉 )，得證。

• 跑 $|V| - 1$ 個回合必可找到最短路，考慮 $s \rightarrow v $ 的最短路徑，

After relax( s , $v_1$ ) in round 1，d[$v_1$] = $c_1$

          relax($v_1$, $v_2$ ) in round 2，d[$v_2$] = $c_1 + c_2$
          $\cdot$
          $\cdot$
          $\cdot$

          relax($v_{k-1}$, $v$) in round $k$，d[$v$] = $c_1 + c_2 + \cdots + c_k$

可知在 $k$ 回合內必可完成更新，又 $k \leq |V| - 1$

由上方這個 Claim ，如果 d[$v$] 在 $|V|$ round 有所改動的話，代表了負環存在

Implementation

做兩次 Bellman-Ford ，偵測出所有負環。
第二次 Bellman-Ford 中，邏輯判斷將d[$v$] 設成 $- \infty$ 的情況共有兩個

• $- \infty$ 的傳染性:

if(dist[e.edge.first] == INT_MIN)
        dist[e.edge.second] = INT_MIN;

• negative cycle 存在於 $s \rightarrow v$ 的最短路中，則將 d[$v$] 設成 $- \infty$

if(dist[e.edge.first] != INT_MAX && dist[e.edge.first] + e.weight < dist[e.edge.second])
        dist[e.edge.second] = INT_MIN;

為什麼還需要再跑 $|V| - 1$ 次？
是因為要將 $- \infty$ 傳染遍整個環，需要負環長度個回合，而最大的負環長度 $\leq |V| - 1$。