使用C/C++語言 楊正宏 編著 全華科技圖書股份有限公司 印行

第八章 圖 形(1/2) 8-1 前言 8-2 圖形的基本觀念 8-3 圖形的資料表示法 8-1 前言 8-2 圖形的基本觀念 8-3 圖形的資料表示法 8-3-1 相鄰矩陣(Adjacency Matrix) 8-3-2 相鄰串列(Adjacency List) 8-3-3 相鄰多重串列(Adjacency Multilist) 8-3-4 索引表格法(Indexed Table)

第八章 圖 形(2/2) 8-4 圖形的追蹤(Graph Traversal) 8-5 擴張樹(Spanning Tree) 8-6 拓樸排序(Topological Sorting) 8-7 最短路徑(Shortest Path)

前言(1/3) 圖形結構提供了簡單的方式來描述一個問題、系統、或狀況等。 與樹狀結構最大的差異是樹狀結構是描述節點與節點之間層次的關係。 瑞士的數學家尤拉(Euler) 解決Koenigsberg bridge problem，這就是著名的七橋問題。

前言(2/3) 3 4 7 A地 D地 5 1 2 6 Koenigsberg bridge

前言(3/3) 尤拉迴路(Eulerian cycle) 邊(Edge)代表各橋，以節點(Vertices)代表4個城市。 C 5 7 3 2 A D 1 4 6 B

圖形的基本觀念 一個圖形(graph)係由有限個節點(Vertices)的集合(V)及節點與節點間相連接邊(Edges)之集合(E)組合而成，我們可以將圖形表為G=(V, E)。 四種圖形結構： 無方向圖形(undirected graph, 簡稱graph) 有方向圖形(directed graph, 簡稱digraph) 相連圖形(connected graph) 不相連圖形(disconnected graph)

無方向圖形(1/9) 圖8-2.2 圖8-2.1 圖8-2.3

無方向圖形(2/9) 重要術語 完整圖形(Complete graph)： 具有n個頂點的無方向圖形，若共有〝n(n-1)/2〞條邊，則稱此無方向圖形為完整圖形(Complete graph)，如圖8-2.1。 相鄰(Adjacent)： 在圖形的某一邊(V1, V2)中我們稱頂點V1與頂點V2是相鄰的。但在有方向圖形中稱<V1, V2>為V1是adjacent to V2或V2是adjacent from V1，如圖8-2.1中V1與V2是adjacent，圖8-2.3中V2與V3也是。 附著(Incident)： 我們稱邊(V1, V2)附著在頂點V1與頂點V2上。我們可發現在圖8-2.3中附著在頂點2的edge有<1, 2>, <2, 1>及<2, 3>。

無方向圖形(3/9) 重要術語 子圖(Subgraph)： G的〝子圖(Subgraph)〞是一個圖G‘，有V(G‘) ≦ V(G)和E(G‘)≦E(G)兩個性質。 路徑(Path)： 圖形中從頂點Vp到頂點Vq的一條路徑是指一串由頂點所成的連續序列Vp, Vi1, Vi2, ..., Vin，Vq其中(Vp, Vi1)，(Vi1, Vi2)….，(Vin, Vq)都是E(G)上的邊。例如：我們將路徑(1, 2)， (2, 4)， (4, 3)寫成1, 2, 3, 4。在圖8-2.1上的兩條路徑，1, 2, 4, 3與1, 3, 4, 2其長度為3。 路徑長度(Path length)： 指路徑上所包含邊的數目稱之為路徑的長度。

無方向圖形(4/9) 重要術語 簡單路徑(Simple path)： 指路徑上除了起點和終點可能相同外，其他的頂點都是不同的。例如：圖8-2.1的1, 2, 4, 3是一條簡單路徑。 循環(Cycle)： 循環(cycle)是一個簡單路徑，其起點與終點為同一個頂點。 連通(Connected)： 無方向圖形中，若從V1到V2有路徑可通，則稱頂點V1和頂點V2是相連的。如果每個的成對頂點Vi, Vj都有路徑由Vi通到Vj,則稱圖形是相連的。 連通單元(Connected component)： 或稱單元(Component)，是指該圖形中最大的連通子圖(maximal connected subgraph)，如下圖8-2.4和圖8-2.5。

無方向圖形(5/9) E F H G D A C B 圖8-2.4 圖8-2.5

無方向圖形(6/9) 圖8-2.6 圖8-2.7 圖8-2.8

無方向圖形(7/9) 圖8-2.6是一個完整圖形。 圖8-2.6中V1與V2是相鄰，圖8-2.8中V4與V5是相鄰。 圖8-2.6中(V1, V2)，(V2, V3)，(V3,V4)，(V4, V5)，(V5, V1)是一條路徑。 圖8-2.6中(V1, V2)，(V2, V3)，(V3, V1)，(V1, V4)，(V4,V5)亦是一條路徑， 圖8.2_6中(V1, V2)，(V2, V3)，(V3, V4)，(V4, V5)這條路徑長度為4。

無方向圖形(8/9) 圖8-2.6中(V1, V2)，(V2, V3)，(V3, V4)，(V4, V5)是一條簡單路徑。 圖8-2.7和圖8-2.8都是圖8-2.6的子圖。 圖8-2.7中(V1, V2), (V2, V4), (V4, V1)是一條循環。 圖8-2.6,圖8-2.7與圖8-2.9都是連通的，圖8-2.8不是連通的。 圖8-2.6有兩個連通單元。

無方向圖形(9/9) 圖8-2.9

有方向圖形(1/4) 重要術語 完整圖形(Complete graph) 路徑(Path) 緊密連通(Strongly Connected) 緊密連通單元(Strongly Connected Component) 多重圖形(multigraph) 分支度(degree) 內分支度(in-degree) 外分支度(out-degree)

有方向圖形(2/4) 圖8-2.13 圖8-2.12 圖8-2.14

有方向圖形(3/4) Eulerian cycle： Eulerian chain： 形成Eulerian cycle的條件是從任何一個頂點開始，經過每個邊一次，再回到出發的那一個頂點時稱之，亦可稱為Eulerian Walk，其充分且必要條件為每個頂點的分支度必須都是偶數。 Eulerian chain： 形成Eulerian的條件是從任何一個頂點開始，經過每邊一次，不一定要回到原出發點時稱之，其充分且必要條件為祇有兩個頂點的分支度是奇數，其餘必須均為偶數。

有方向圖形(4/4) 1 2 3 4 5 1 2 3 4 5 圖8-2.15 Eulerian cycle 圖8-2.16 Eulerian chain

圖形的資料表示法 相鄰矩陣(Adjacency Matrix) 相鄰串列(Adjacency List) 相鄰多重串列(Adjacency Multilist) 索引表格法( Indexed Table)

相鄰矩陣(1/3) 將圖形中的n個頂點(Vertices)，以一個n × n的二維矩陣來表示，其中若A(i, j)=1，則表示graph中有一條邊(Vi, Vj)存在。反之，A(i, j)=0則沒有。 圖8-3-1.1

相鄰矩陣(2/3) 相鄰矩陣 圖8-3-1.2

相鄰矩陣(3/3) 無方向圖形之相鄰矩陣是具備對稱性的，且對角線皆為零，所以在圖形中只需要儲存上三角形或下三角形即可，所需要儲存空間為n(n-1)/2。 若要求無方向圖中某一頂點相鄰邊的數目(即分支度)，只要算算相鄰矩陣中某一列所有1的和或某一行所有1的和。 若要求有方向圖形的內分支度或外分支度。相鄰矩陣裡，列中的1之和便是外分支度，而行中的1之和，便是內分支度。

相鄰串列(1/2) 將圖形中的每個頂點皆形成串列首，而在每個串列首後的節點表示它們之間有邊相連。 每個節點結構 圖8-3-2.1 Vertex Link 圖8-3-2.1

相鄰串列(2/2) 相鄰串列 圖8-3-2.2

相鄰多重串列 節點的結構： M V1 V2 Link1 for V1 Link2 for V2 1 3 4 2 圖8-3-3.1

索引表格法(1/2) 為一種儲存圖形的資料結構，採用一維陣列儲存頂點，建立一索引表格並且對應到相當的位置。 操作方式： 以一個一維陣列來循序儲存相鄰頂點。 建立一個索引表格，n個頂點須建立n個位置於索引表格中，分別對應於陣列中與第一個與該頂點相鄰的位置。

索引表格法(2/2) B C D 圖8-3-4.1 A

圖形的追蹤(Graph Traversal) 圖形是由有限個節點組合而成，節點與節點之間是由邊相互連接，對於每個節點之拜訪順序，也就是圖形之追蹤。 二種追蹤法： 深度優先搜尋法(Depth First Search, DFS) 廣度優先搜尋法(Breadth First Search, BFS)

深度優先搜尋法(1/2) 以縱向為先，首先選定一個任意節點，假設為V0，由拜訪V0開始。 V0的相鄰節點有V1，V2，…，Vi；然後拜訪V1，再拜訪V1的相鄰節點中的某一節點，如此一直重覆。 若其所有相鄰節點均已被拜訪過，則回到上一個被拜訪過的節點，它還含有未被拜訪過的相鄰節點Vp，就再拜訪Vp。

深度優先搜尋法(2/2) 拜訪可能順序： V1 V2 V4 V5 V6 V3 V1 V2 V4 V6 V5 V3 圖8-4.1 2 4 1

廣度優先搜尋法(1/2) 任意選擇某一個開始的節點，假設它為V0，因此先拜訪V0然後以任意的順序去拜訪V0的相鄰節點。 假設V0的相鄰節為V1，V2，…，Vi，當這些節點都拜訪過後，再接著拜訪V1的相鄰節點。 當V1相鄰節點都拜訪過後，再拜訪V2的相鄰節點，如此重覆直到圖形上的所有節點都被拜訪過。

廣度優先搜尋法(2/2) 拜訪可能順序： V1 V2 V3 V4 V5 V6 V1 V3 V2 V4 V5 V6 圖8-4.1 2 4 1 6 3 5

圖形的追蹤範例(1/2) 求下圖之DFS與BFS之搜尋順序。 1 3 2 4 5 6 7 8 圖8-4.2 1 2 3 4 5 6 7 圖8-4.3

圖形的追蹤範例(2/2) 圖8-4.2解答： 圖8-4.3解答： DFS搜尋順序：1→2→4→8→5→6→3→7 BFS左先搜尋：1→2→3→4→5→6→7→8 BFS右先搜尋：1→3→2→7→6→5→4→8 圖8-4.3解答： DFS搜尋順序：1→2→5→6→3→7→4 BFS左先搜尋：1→2→3→4→5→6→7 BFS右先搜尋：1→4→3→2→7→6→5

擴張樹(Spanning Tree) 在一個非方向圖形中以最少的邊線連結起所有頂點，而連結後卻不會形成迴圈，稱 之。 一擴張樹中任兩個點間，只有一條路徑可通。 由於拜訪節點的順序不同，因此產生兩種不同的擴張樹： 深度優先搜尋法擴張樹(Depth First Search Spanning Tree)：以深度優先搜尋方式產生的擴張樹。 廣度優先搜尋法擴張樹(Breadth First Search Spanning Tree)：廣度優先搜尋法方式產生的擴張樹。

擴張樹範例(1/4) 繪出擴張樹 <解>產生三個擴張樹 圖8-5.1 圖8-5.2

擴張樹範例(2/4) 求DFS擴張樹和BFS擴張樹 1 2 3 4 5 6 7 圖8-5.6 1 3 2 4 5 6 7 8 圖8-5.3

擴張樹範例(3/4) 圖8-5.3 之DFS擴張樹 圖8-5.3 之BFS擴張樹 圖8-5.4 圖8-5. 5 DFS為1→2→4→8→5→6→3→7 BFS為1→2→3→4→5→6→7→8

擴張樹範例(4/4) 圖8-5.6 之DFS擴張樹 圖8-5.6 之BFS擴張樹 1 2 3 4 5 6 7 圖8-5.8 圖8-5.7 1

最小成本擴張樹 (Minimum Cost Spanning Tree) 含有權重之邊線造成之擴張樹其權重總和會有所不同，其每邊的加權值之和是最小者，則稱之。 以最少成本為原則，須滿足下列限制： 只能使用這個圖裡的邊。 只能使用n-1個邊(若有n個節點)。 所使用的邊不能產生一個環路。 兩種方法： 克如斯卡(Kruskal)法 普瑞(Prim’s)法

Kruskal 將整個圖形所有邊線之權重依小到大列出一表。 由權重最小者開始做連接工作，若連接結果不會造成迴圈則成立，若造成迴圈則不予採用。 演算法： 令花費最少之擴張樹 T =  。 從E中選取花費最少的邊(Vx, Vy)(2)。 如果(Vx, Vy)不會使T產生迴路則將之加入T中，否則自E中刪除(3)。 重複 (2) 和(3) 步驟，直到T的邊等於n-1為止。

Kruskal範例(1/3) 利用克如斯卡法算出下圖的最小成本擴張樹 圖8-5.9 2 1 6 5 4 3 17 14 12 19 31 16 9

Kruskal範例(2/3) 列出整個圖形之權重表

Kruskal範例(3/3) 結果： 圖8-5.10 14 cost=46 3 1 4 2 5 6 16 9

Prim’s (1)從任一頂點開始，找出其權重最輕的一條邊。 (2)由此兩點向外再找，找一條權重最輕的邊線連接起來唯，這個權重次輕的邊線必須與剛才相連接的頂點相接。 (3)利用規則(2)將所有頂點相連，但不可造成迴圈。 建立擴張樹步驟： 令A=V，B= ，T= 。 從A中任選一的頂點，將之從A搬移至B，並加入T。 找出一條連接A和B的最少花費邊E (a, b) ，其中aA，bB，且邊(a, b)加到T不會造成迴路(c)。 將頂點a自A搬移到B，並將頂點a 與邊（a, b）加入T(d)。 重複(c)，(d) 直到A= 。

Prim’s範例(1/6) 利用普瑞法求最小成本擴張樹 圖8-5.13 2 1 6 5 4 3 17 14 12 19 31 16 9

Prim’s範例(2/6) 解題步驟 步驟一：令Ａ集合為{1, 2, 3, 4, 5, 6}，Ｂ集合為 ，則Ｔ為。 步驟二：取頂點“1”，故Ａ集合為{2, 3, 4, 5, 6}，Ｂ集合為{1} ，則Ｔ為： 步驟三：可選路徑有：(1, 2)=14，(1, 6)=19，(1, 5)=17 ，取頂點“2”，得(1, 2)=14，而故Ａ集合為{3, 4, 5, 6}，Ｂ集合為{1, 2} ，則Ｔ為

Prim’s範例(3/6) 解題步驟 步驟四：可選路徑有：(1, 5)=17，(1, 6)=19，(2, 6)=9，(2, 4)=4，(2, 3)=3，取頂點“3”，得(2, 3)=3，Ａ集合為{4, 5, 6}，Ｂ集合為{1, 2, 3}，則Ｔ為

Prim’s範例(4/6) 解題步驟 步驟五：可選路徑有：(1, 5)=17, (1, 6)=19，(2, 6)=9, (2,4)=4, (3,4)=8取頂點“4”，得(2, 4)=4，Ａ集合為{ 5, 6}，Ｂ集合為{1, 2, 3, 4}，則Ｔ為：

Prim’s範例(5/6) 解題步驟 步驟六：可選路徑有：(1, 5)=17, (1, 6)=19，(2, 6)=9，(3,4)=8，(4,5)=16，(4,6)=12，放棄路徑(3, 4)，因為已造成迴路。取頂點“6”，得(2, 6)=9，Ａ集合為{ 5}，Ｂ集合為{1, 2, 3, 4, 6}，Ｔ則為：

Prim’s範例(6/6) 解題步驟 步驟七：由於步驟大都相同故省略一些小細節。取頂點“5”，得(4, 5)=16，而Ａ為，故結束搬移。最後得答案Ｔ則為： 14 3 1 4 2 5 6 16 9 圖8-5.14

拓樸排序(Topological Sorting) 用來分析整個AOV網路，將網路中事件的優先次序以線性方式列出來。 先從內分支度為0的節點開始，因內分支度為0表示此節點沒有先行者（Predecessor），所以可先完成此節點延伸的點，然後將此節點所延伸的工作都予以刪除，再由內分支度為0的節點繼續輸出拓撲順序（Topological ordering）。

拓樸排序範例(1/3) 由於節點1沒有內分支度，因為首先輸出拓撲順序為V1，然後將V1所引出的邊刪除。 2 4 1 3 5 圖8-6.1 圖8-6.2

拓樸排序範例(2/3) 由於節點2沒有內分支度，所以輸出拓撲順序為V2，然後將V2所引出的邊刪除。 4 2 3 5 圖8-6.2 圖8-6.3

拓樸排序範例(3/3) 重覆此步驟直到最後…（如圖8-6.4至圖8-6.6所示），所以整個拓撲順序為V1，V2，V3，V4，V5。 圖8-6.5 圖8-6.6

拓樸排序 無法做拓撲排序的圖形如圖8-6.7所示，到輸出V2時，此時圖形如圖8-6.9所示，其中已經沒有一個節點的內分支度為0了，因此做拓撲排序時，網路一定不能有循環存在。 2 4 1 3 5 圖8-6.9 圖8-6.7 圖8-6.8

最短路徑 圖形的每個邊都給予加權值，此加權值可能是成本或距離，這個圖形即可構成一個網路系統。 在這個網路系統中，選擇一個起始節點叫Vs，另外選擇一個終止節點叫Vt，如何求出由Vs到Vt的最短距離就是最短路徑（Shortest Path）。 網路系統上，三個常用到的最短路徑： 由某一個固定節點到另一個固定節點的最短路徑。 由某一個固定節點到其他各節點的最短路徑。 由各節點到其他各節點的最短路徑。

Dijkstra 演算法 設L為N個位置的陣列，用來儲存由某點到各點的最短距離，B為某一個起始點，A[B, I]表示為B點到I點的距離，V是網路中所有項點的集合，S亦是節點的集合。 設定L[I] = A[B,I]（I = 1,N）（B為固定節點） S = [B], V = [1,2,…, N] 假如｛V-S｝是空集合，則停止，否則找到一個K節點使得 L[K]是極小值，並把K放入集合S中。 根據下列原則調整陣列L中之值。 L[I] = min（L[I], L[K] + A[K,I]）（（I,K） E） （此處I是指與K相鄰的各節點），回到步驟2繼續執行。

Dijkstra範例(1/6) 圖8-7.1表示的是台灣幾個重要的城市，邊是兩城市之間所需花費的成本，以相鄰矩陣A表示，如圖8-7.2 ，試求台北到南投需花費的最小成本。 台南 高雄 30 台東 圖8-7.1 2 3 8 7 9 5 4 1 6 花蓮 新竹 台中 屏東 南投 40 45 50 80 100 台北 150 20 1 2 3 4 5 6 7 8 9 1 0 40 ∞ ∞ ∞ ∞ ∞ 45 80 2 ∞ 0 45 ∞ ∞ ∞ ∞ ∞ ∞ 3 ∞ ∞ 0 50 ∞ ∞ ∞ ∞ ∞ 4 ∞ ∞ ∞ 0 30 ∞ ∞ ∞ ∞ 5 ∞ ∞ ∞ ∞ 0 40 ∞ ∞ ∞ 6 ∞ ∞ ∞ ∞ ∞ 0 ∞ ∞ ∞ 7 ∞ ∞ ∞ ∞ ∞ 150 0 ∞ ∞ 8 ∞ ∞ ∞ ∞ ∞ ∞ 40 0 20 9 ∞ ∞ ∞ ∞ 100 ∞ ∞ ∞ 0 8-7.2

Dijkstra範例(2/6) 假設有一人要從台北到高雄，應如何走才最有效率，亦即是如何求出台北至高雄的最短距離。 從台北出發，所以F=1；S={1}，V={1, 2, 3, 4, 5, 6, 7, 8，9}，L={0,40, ∞, ∞,∞,∞,∞,45,80}；L陣列的L[2]=40表示從台北到新竹的成本為40，L[3]=∞表示從台北到台中的成本為無窮大。從L陣列可比較出L[2]的成本最少，因此把頂點2加入S陣列中，於是S={1, 2}，V-S={ 3, 4, 5 ,6, 7, 8, 9}，而且與頂點2相鄰的頂點為頂點3，即 L[3]=min(L[3], D[2]+A[2,3])=min(∞,40+45)=85 此時L陣列變成L={0,40,85,∞,∞,∞,∞,45,80}。

Dijkstra範例(3/6) 從V-S={3, 4, 5 ,6, 7, 8, 9}中找出L陣列成本最小的，即L[8]=45，因此將頂點8加入S陣列，於是S={1,2,8}，V-S{ 3, 4, 5 ,6, 7, 9}，而且與頂點8相鄰的頂點為頂點7和頂點9，即 L[7]=min(L[7], L[8]+A[8,7])=min(∞, 45+40)=85 L[9]=min(L[9], L[8]+A[8,9])=min(80, 45+20)=65 此時L陣列變成L={0,40,85,∞,∞,∞,85,45,65}。 從V-S={ 3, 4, 5 ,6, 7, 9}中找出L陣列成本最小的，即L[9]=65，因此將頂點9加入S陣列，於是S={1,2,8,9}，V-S{ 3, 4, 5 ,6, 7}，而且與頂點9相鄰的頂點為頂點5，即 L[5]=min(L[5], L[9]+A[9,5])=min(∞, 65+100)=165 此時L陣列變成L={0,40,85,∞,165,∞,85,45,65}。

Dijkstra範例(4/6) 從V-S={3, 4, 5 ,6, 7}中找出L陣列成本最小的，即L[3]=85，因此將頂點3加入S陣列，於是S={1,2,3,8,9}，V-S{ 4, 5 ,6, 7}，而且與頂點3相鄰的頂點為頂點4，即 L[4]=min(L[4], L[3]+A[3,4])=min(∞, 85+50)=135 此時L陣列變成L={0,40,85,135,165,∞,85,45,65}。 從V-S={4, 5 ,6, 7}中找出L陣列成本最小的，即L[7]=95，因此將頂點7加入S陣列，於是S={1,2,3,7,8,9}，V-S{ 4, 5 ,6}，而且與頂點7相鄰的頂點為頂點6，即 L[6]=min(L[6], L[7]+A[7,6])=min(∞, 85+150)=235 此時L陣列變成L={0,40,85,135,165,235,85,45,65}。

Dijkstra範例(5/6) 從V-S={ 4, 5 ,6}中找出L陣列成本最小的，即L[4]=135，因此將頂點4加入S陣列，於是S={1,2,3,4,7,8,9}，V-S{5 ,6}，而且與頂點4相鄰的頂點為頂點5，即 L[5]=min(L[5], L[4]+A[4,5])=min(165, 135+30)=165 此時L陣列變成L={0,40,85,135,165,235,85,45,65}。 從V-S={5 ,6}中找出L陣列成本最小的，即L[5]=165，因此將頂點5加入S陣列，於是S={1,2,3,4,5,7,8,9}，V-S={6}，而且與頂點5相鄰的頂點為頂點6，即 L[6]=min(L[6], L[5]+A[5,6])=min(235, 165+40)=205 此時L陣列變成L={0,40,85,135,165,205,85,45,65}。

Dijkstra範例(6/6) 最後V-S陣列只剩6，將6加入S陣列中，於是V-S為一空集合。此時可由L陣列看出頂點1到其它節點所花費的最小成本，台北到南投的最小成本是65。

Warshall’ s 演算法 Q(e) ,若存在一個Vi到Vj的邊。 Qi j = ∞ ,沒有Vi到Vj的邊。 設G是一個有m個節點V1，V2，…，Vm且有加權的有向圖形。亦即G中的每一邊e，給予一個加權值Q(e)。於是G便可以用矩陣Q=(Qij)的形式表示如下： 將圖形G以相鄰矩陣Q0來表示。 根據下列原則來調整矩陣Qk中之值： Qk[i,j]=min(Q k-1[i,j] , Qk-1[i,k]+ Qk-1[k,j]) 其中最後一個矩陣Qm就是我們所求的矩陣。 Q(e) ,若存在一個Vi到Vj的邊。 Qi j = ∞ ,沒有Vi到Vj的邊。

Warshall’ s範例(1/5) 試求台北到南投需花費的最小成本。 Q0 = 將圖8-7.1以相鄰矩陣Q0表示： 1 2 3 4 5 6 7 8 9 1 0 40 ∞ ∞ ∞ ∞ ∞ 45 80 2 ∞ 0 45 ∞ ∞ ∞ ∞ ∞ ∞ 3 ∞ ∞ 0 50 ∞ ∞ ∞ ∞ ∞ 4 ∞ ∞ ∞ 0 30 ∞ ∞ ∞ ∞ 5 ∞ ∞ ∞ ∞ 0 40 ∞ ∞ ∞ 6 ∞ ∞ ∞ ∞ ∞ 0 ∞ ∞ ∞ 7 ∞ ∞ ∞ ∞ ∞ 150 0 ∞ ∞ 8 ∞ ∞ ∞ ∞ ∞ ∞ 40 0 20 9 ∞ ∞ ∞ ∞ 100 ∞ ∞ ∞ 0 Q0 =

Warshall’ s範例(2/5) 根據下列原則來調整矩陣Q1中之值： Q1[i,j]=min(Q0[i,j] , Q0[i,k]+ Q0[k,j]) 1 2 3 4 5 6 7 8 9 1 0 40 ∞ ∞ ∞ ∞ ∞ 45 80 2 ∞ 0 45 ∞ ∞ ∞ ∞ ∞ ∞ 3 ∞ ∞ 0 50 ∞ ∞ ∞ ∞ ∞ 4 ∞ ∞ ∞ 0 30 ∞ ∞ ∞ ∞ 5 ∞ ∞ ∞ ∞ 0 40 ∞ ∞ ∞ 6 ∞ ∞ ∞ ∞ ∞ 0 ∞ ∞ ∞ 7 ∞ ∞ ∞ ∞ ∞ 150 0 ∞ ∞ 8 ∞ ∞ ∞ ∞ ∞ ∞ 40 0 20 9 ∞ ∞ ∞ ∞ 100 ∞ ∞ ∞ 0 Q1 =

Warshall’ s範例(3/5) 根據下列原則來調整矩陣Q2中之值： Q2[i,j]=min(Q1[i,j] , Q1[i,k]+ Q1[k,j]) 1 2 3 4 5 6 7 8 9 1 0 40 85 ∞ ∞ ∞ ∞ 45 80 2 ∞ 0 45 ∞ ∞ ∞ ∞ ∞ ∞ 3 ∞ ∞ 0 50 ∞ ∞ ∞ ∞ ∞ 4 ∞ ∞ ∞ 0 30 ∞ ∞ ∞ ∞ 5 ∞ ∞ ∞ ∞ 0 40 ∞ ∞ ∞ 6 ∞ ∞ ∞ ∞ ∞ 0 ∞ ∞ ∞ 7 ∞ ∞ ∞ ∞ ∞ 150 0 ∞ ∞ 8 ∞ ∞ ∞ ∞ ∞ ∞ 40 0 20 9 ∞ ∞ ∞ ∞ 100 ∞ ∞ ∞ 0 Q2 = 在矩陣中Ｑ2[1,3]= min(Q1[1,3] , Q1[1,2]+ Q1[2,3])=85

Warshall’ s範例(4/5) 根據下列原則來調整矩陣Q3中之值： Q3[i,j]=min(Q2[i,j] , Q2[i,k]+ Q2[k,j]) 1 2 3 4 5 6 7 8 9 1 0 40 85 135 ∞ ∞ ∞ 45 80 2 ∞ 0 45 95 ∞ ∞ ∞ ∞ ∞ 3 ∞ ∞ 0 50 ∞ ∞ ∞ ∞ ∞ 4 ∞ ∞ ∞ 0 30 ∞ ∞ ∞ ∞ 5 ∞ ∞ ∞ ∞ 0 40 ∞ ∞ ∞ 6 ∞ ∞ ∞ ∞ ∞ 0 ∞ ∞ ∞ 7 ∞ ∞ ∞ ∞ ∞ 150 0 ∞ ∞ 8 ∞ ∞ ∞ ∞ ∞ ∞ 40 0 20 9 ∞ ∞ ∞ ∞ 100 ∞ ∞ ∞ 0 Q3 = 在矩陣中Ｑ3[1,4]= min(Q2[1,4] , Q2[1,3]+ Q2[3,4])=135 在矩陣中Ｑ3[2,4]= min(Q2[2,4] , Q2[2,3]+ Q2[3,4])=95

Warshall’ s範例(5/5) 以此類推，最後所得到的陣列Ｑ9即是各點之間的最短路徑。 Q9 = 如Ｑ9[1,6]=205表示為台北 到屏東的最短路徑；Ｑ9[8,6]=160表示為花蓮到屏東的最短路徑。台北到南投的最短路徑為Ｑ9[1,9]=65。 1 2 3 4 5 6 7 8 9 1 0 40 85 135 165 205 85 45 80 2 ∞ 0 45 95 125 165 ∞ ∞ ∞ 3 ∞ ∞ 0 50 80 120 ∞ ∞ ∞ 4 ∞ ∞ ∞ 0 30 70 ∞ ∞ ∞ 5 ∞ ∞ ∞ ∞ 0 40 ∞ ∞ ∞ 6 ∞ ∞ ∞ ∞ ∞ 0 ∞ ∞ ∞ 7 ∞ ∞ ∞ ∞ ∞ 150 0 ∞ ∞ 8 ∞ ∞ ∞ ∞ 120 160 40 0 20 9 ∞ ∞ ∞ ∞ 100 140 ∞ ∞ 0 Q9 =