1 Edge detection

• 由 Cut Property 可知：如果 e 是從某個集合 S 到補集 V?S 的開銷最小的邊，則 e 一定所有最小生成樹中。

• 由 Cycle Property 可知：如果 e 是某個環 C 上開銷最大的邊，則 e 一定不在最小生成樹中。

所以，根據以上兩點可以知道判斷邊 e = (v, w) 是否屬于 G 最小生成樹的條件：
當且僅當 v 和 w 可以通過完全由比 e 開銷更小的邊組成的路徑連接時，邊 e 不屬于 G 的最小生成樹。

基于此設計算法：

1. 從圖 G 中刪除所有開銷大于等于 e 的所有邊，形成圖 G' 。這一步驟的運行時間是 $O(m+n)$
2. 通過 BFS 或 DFS 確定在 G' 中是否存在從 v 到 w 的路徑。這一步驟的運行時間是 $O(m+n)$
   • 若沒有這樣的路徑，邊 e 屬于 G 的最小生成樹。
   • 若有這樣的路徑，邊 e 不屬于 G 的最小生成樹。

通過以上算法可以判斷 e 是否屬于 G 的最小生成樹，且運行時間是 $O(m+n)$

---

2 Reachability

• 先通過強連通分支算法獲取圖 G 的連通分支圖 G'，并將 G' 內所有點的值標記為 G' 中 點的最小值。運行時間是 $O(V+E)$

• 對于圖 G'，執行以下函數，該函數至多被執行 $V+E$ 次。運行時間是 $O(V+E)$

REACHABILITY(u)u.min = u.labelfor each v ∈ Adj[u]u.min = min(u.min, REACHABILITY(v))return u.min

• 對于圖 G ，min(u) 的值為：G' 圖中的 min(u')

---

3 Bitonic shortest paths

根據 Bellman-Ford算法進行改進，以執行更少的松弛操作。

在任何一個雙調路徑中，最多有兩個不同的遞增序列和兩個不同的遞減序列。因此，通過路徑松弛性質，按照權重遞增的順序松弛邊兩次，再按照權重遞減的順序松弛邊兩次，就可以確保對于 $?v\in V$，$v.d=\delta (s,v)$。

此時有運行時間：

• 對邊進行排序：$O(E\lg E)$
• 總共四次松弛：$O(E)$

所以，總共的運行時間是 $O(E\lg E)+O(E)=O(E\lg E)$，相比普通 Bellman-Ford算法的 $O(VE)$ 更快。

---