講師:郭育倫 d95037@csie.ntu.edu.tw 第10章 加權圖 講師:郭育倫 d95037@csie.ntu.edu.tw

演算法導論，探矽工作室 本章學習重點 最小生成樹 最短路徑

摘要 最小生成樹 最短路徑 Prim演算法 Kruskal演算法 Dijkstra演算法 Bellman-Ford演算法 演算法導論，探矽工作室 摘要 最小生成樹 Prim演算法 Kruskal演算法 最短路徑 Dijkstra演算法 Bellman-Ford演算法 Floyd-Warshall演算法

加權圖 有些圖形化的問題除了節點的連通性外，還需要考慮邊線的權值。 演算法導論，探矽工作室 加權圖 有些圖形化的問題除了節點的連通性外，還需要考慮邊線的權值。 加權圖演算法通常是用來解決最佳化的問題。例如，如何降低連結所有節點的成本就是一個常見的應用。

最小生成樹 加權圖的生成樹是指連接所有節點的子圖。最小生成樹的意思是指其邊線權值總和為最小的生成樹。 演算法導論，探矽工作室 最小生成樹 加權圖的生成樹是指連接所有節點的子圖。最小生成樹的意思是指其邊線權值總和為最小的生成樹。 圖形搜尋樹也是最小生成樹的一種，只不過圖形搜尋樹是將邊線的權值都視為相同。 圖形的最小生成樹並不是唯一。選擇邊線的規則不同就會導致不同的生成樹。

演算法導論，探矽工作室 Prim演算法 建立最小生成樹的基本原理是，把所有節點分成兩個集合，其中一個集合構成最小生成樹的子圖。這個子圖再藉由選擇連接兩個集合間距離最短(即權值最小)的邊線而長大。當所有節點都已加入此生成樹的集合以後，即完成最小生成樹的建立。 Prim所提出的演算法利用優先權佇列將相鄰節點予以排序，並取出距離最短的節點作為生成樹的集合。

演算法導論，探矽工作室 Prim演算法範例

演算法導論，探矽工作室 Prim演算法分析 Prim的最小生成樹演算法可說是一種貪婪法。在建構最小生成樹的過程中，只考慮與最小生成樹相鄰的邊線，並從中挑選最小權值的邊線。 貪婪演算法在大部分的情形下確實可達到最佳化的結果，像Prim演算法就是其中一種。Prim的演算法是正確的，因為其最小生成樹結果一定包含最小權值的相鄰邊線，否則就會違反最小生成樹的定義。

Kruskal演算法 Kruskal直接依權值將所有邊線進行排序，然後再依序挑選邊線，避開形成迴路的邊線，直到形成一個生成樹。 演算法導論，探矽工作室 Kruskal演算法 Kruskal直接依權值將所有邊線進行排序，然後再依序挑選邊線，避開形成迴路的邊線，直到形成一個生成樹。

演算法導論，探矽工作室 Kruskal演算法範例

演算法導論，探矽工作室 Kruskal演算法分析 在Prim演算法中，因為是由小樹長成大樹，所以檢驗迴路的動作比較單純，不過卻需要考慮選擇邊線時的效能。而Kruskal演算法，則因所有邊線已經過排序，所以沒有選擇邊線的運算，但是其檢查迴路的動作卻較為複雜。因此，如果圖形的邊數較多(即茂密圖)，那麼選擇Prim演算法會比較有效率，反之則建議採用Kruskal演算法。

最短路徑 最短路徑的定義是兩個節點之間其經過的邊線權值和為最小。最短路徑的問題可以分成兩類: 演算法導論，探矽工作室 最短路徑 最短路徑的定義是兩個節點之間其經過的邊線權值和為最小。最短路徑的問題可以分成兩類: 單源最短路徑 任意兩節點之最短路徑 單源最短路徑可得到從某一起點到其他節點的最短路徑，而任意兩節點之最短路徑顧名思義即是計算任意兩個節點之間，其所經過的邊線權值和為最小的路徑。

演算法導論，探矽工作室 最短路徑的放鬆 最短路徑演算法當中經常使用到的一個技巧：最短路徑的放鬆。這個方法的精神是，如果某節點Y可抵達X，而且經過節點Y可以縮短起點到X的距離，那麼就將節點Y加入此路徑並更新到X的最短距離。

演算法導論，探矽工作室 Dijkstra演算法 Dijkstra演算法是利用貪婪法解決單源最短路徑的問題。這個演算法的想法是藉由逐步建立最短路徑生成樹的過程來求得最短路徑。 優先權佇列再度被用來排序相鄰節點的最短路徑估算值。每次從佇列中取出相鄰的節點，再依據「最短路徑放鬆」的原則判斷是否需要更新相鄰邊線的最低權值和。

演算法導論，探矽工作室 Dijkstra演算法範例

演算法導論，探矽工作室 Dijkstra演算法分析 Dijkstra演算法也可應用在有向圖形，而唯一的限制是邊線的權值不能是負數。負權值的邊線有時候會誤導Dijkstra演算法並產生錯誤的結果。

演算法導論，探矽工作室 Bellman-Ford演算法 Bellman和Ford改用動態程序規劃的觀念來解決單源最短路徑問題。和Dijkstra以相鄰節點進行「最短路徑放鬆」不同的是，Bellman-Ford演算法是直接對每條邊線實施「最短路徑放鬆」。 Bellman-Ford演算法利用反覆檢查每條邊線來逼近每個節點其最短路徑的估計值。因為圖形的最長路徑是V-1 條邊線，因此最多只要檢查V-1遍就可以建構出最短路徑生成樹。

演算法導論，探矽工作室 Bellman-Ford演算法範例

演算法導論，探矽工作室 Floyd-Warshall演算法 假如節點X存在一條路徑通往節點W，而W又存在一路徑通往Y，這樣一來就能肯定節點X可以通往Y。這個性質在數學上稱為遞移封閉性。數學家Warshall從這個簡單的原理，發展出一個演算法可以求得任意兩節點之間是否存在一路徑。 數學家Floyd利用Warshall演算法的精神，考慮任意兩節點間的最短路徑。如果節點X到Y的距離，可以因為節點W的加入而縮短，那就將W加入X和Y之間的最短路徑。

演算法導論，探矽工作室 遞移矩陣範例

演算法導論，探矽工作室 任意兩節點最短路徑範例

演算法導論，探矽工作室 結論 此章節探討加權圖相關的演算法，其包括典型的最小生成樹與最短路徑問題。雖然我們所討論的範例是以無向圖為主，但事實上這些演算法也可應用在有向圖形。 我們也在介紹了貪婪演算法和動態程序規劃演算法的基本概念。比如Prim演算法和根據貪婪法的精神而設計出來的Dijkstra演算法；而Bellman-Ford演算法和Floyd-Warshall演算法則有運用動態程序規劃的技巧。這些概念可以作為往後我們在面臨新問題時的思考解決之道。