資料結構與演算法教學系列文 (9) - 圖的進階議題
圖的進階議題（Advanced Topic on Graph）
最短路徑（Shortest Path）
最短路徑問題（Shortest Path Problem）是圖論中的一個重要課題，目的是尋找從一個起始節點到其他節點的最短路徑。相關的應用像是地圖中的導航系統、網路路由選擇等等，背後都是使用最短路徑的演算法。
戴克斯特拉演算法（Dijkstra’s Algorithm）
戴克斯特拉演算法是一種廣泛使用的方法，特別適用於權重非負的有向圖和無向圖，通過不斷選擇當前距離最小的未訪問節點，並更新其所有相鄰節點的最短距離，來尋找從起始節點到其他所有節點的最短路徑。
特別要注意的是，若存在負權重的邊，則戴克斯特拉演算法就不再適用。為什麼？讓我們看看以下的圖：
你想到原因了嗎？在這張圖中，使用戴克斯特拉演算法會發生什麼事情？
Bellman–Ford Algorithm
相較於戴克斯特拉演算法，Bellman–Ford Algorithm 可以用在含有負權重邊的情況，是一種能處理負權重邊的最短路徑演算法。
Bellman–Ford 的核心步驟是反覆對所有邊做 Relaxation（檢查是否可以利用某條邊縮短當前已知的最短路徑距離，若可以則更新），經過 V−1 次 Relaxation 的操作後（V 為節點數），可以找到從起點到其他所有節點的最短路徑。
雖然可以處理包含負權重邊的圖，但圖中不能存在負權重環（總和為負的環）。為什麼？
若圖中存在負權重環，我們可以一直在這個環中不斷遍歷，就會造成最短路徑變為負無限大。
反過來說，若在 V−1 次放鬆後，還有可以縮短的路徑，則代表該圖中存在負權重環，因此最短路徑不存在。
因此，Bellman–Ford 不僅適用於包含負權重邊的圖，還可以檢測負權重環。
Floyd-Warshall Algorithm
Floyd-Warshall 演算法用於解決所有點對最短路徑問題（All-Pairs Shortest Paths Problem），是一種基於動態規劃的方法。與 Dijkstra 和 Bellman-Ford 不同的是，Floyd-Warshall 可以計算算任意兩個節點之間的最短路徑。
其主要的想法是：假設我們要從節點 i 到節點 j 找最短路徑，若能經由中間節點 k 獲得更短的距離，那麼我們就更新該最短路徑。用遞迴公式表示如下：$d[i][j] = min(d[i][j], d[i][k] + d[k][j])$。因此我們總共需要做 V 次更新，每次都檢查各點對之間的距離是否有更佳解。
Leetcode
- 743. Network Delay Time
- 1334. Find the City With the Smallest Number of Neighbors at a Threshold Distance
生成樹（Spanning Tree）
從一張圖取出一棵樹，樹上可以連接圖上所有點，就稱為該圖的生成樹，一個圖可能有不只一種生成樹。
最小生成樹（Minimum Cost Spanning Tree）
顧名思義，最小生成樹就是最小的生成樹，這邊的最小指的是「連接所有節點所需的花費（所有邊的花費總和）最小」。
以下為兩個常見且易懂的貪婪演算法，來尋找圖中的最小生成樹：
Kruskal’s algorithm
不斷從所有邊裡面選花費最小的邊，並判斷加入此邊可否連通兩個不同的 Component，直到所有的節點都被相連。（以所有邊作為每輪檢查的對象）
Prim’s Algorithm
選定一個起點，挑選與其連接的邊中，花費最小且可連接兩個不同 Component 的相連，再把新連接的所有邊加入下一輪的檢查。其精神與 Dijkstra’s Algorithm 有幾分類似。（以目前相連的點包含的所有邊，作為每輪檢查的對象）
備註：也有所謂的最大生成樹，概念一模一樣
Leetcode
有向無環圖（Directed Acyclic Graph）與拓樸排序（Topological Sorting）
有向無環圖（Directed Acyclic Graph）又稱 DAG，顧名思義，是有方向且不包含環的 Graph。
拓樸排序（Topological Sorting）是一種將 DAG 中的所有節點排序的方式，使得每條有向邊的排序符合其方向性（舉例來說：u->v->w 的拓樸排序為 [u, v, w]）。因為 DAG 之中不會有環，故只要是 DAG 則必能找到一個拓樸排序。
以下介紹一個在 DAG 中尋找拓樸排序的方法：
Kahn’s Algorithm
透過找出圖中的 in-degree 為零的節點，逐步移除這些節點，並同時更新圖的 in-degree，從而達到拓樸排序。
- 若所有節點皆能被移除，則移除順序即為拓樸排序
- 若無法移除所有節點，則代表圖中有環（因此此圖不會是 DAG）
Leetcode
