Embedded Files
一、實作圖形資料結構—新增邊的權重
二、使用Dijkstra演算法找最短路徑
三、使用Bellman Ford演算法找最短路徑
四、使用Floyd Warshall演算法找最短路徑
圖形資料結構是由點與邊所組成，圖形資料結構廣泛應用於程式的實作，許多功能的實作都可以轉換成圖形資料結構，例如：使用地圖搜尋最短路徑，將地點轉換成圖形資料結構中的點，地點與地點間的距離轉換成邊的權重，最後使用最短路徑演算法就可以找出最短路徑。
一、實作圖形資料結構—新增邊的權重
實作邊帶有權重的圖形資料結構，讓讀者可以更加瞭解圖形資料結構，並介紹圖形資料結構的最短路徑演算法，如何利用程式找出起點到每個節點的最短路徑。
(ㄧ)使用陣列建立邊帶有權重的圖形資料結構
可以使用陣列建立圖形資料結構，如下圖形資料結構範例，本範例圖形結構有5個節點，可以使用5x5的陣列儲存下圖。
若有邊相連，則陣列元素值改為邊的權重，否則陣列元素值改為0。由下表可知無向圖一定是對稱陣列，因為點x可以連到點y，點y一定可以連回點x。
有向圖也可以使用陣列建立圖形資料結構，如下圖形資料結構範例，本範例圖形結構有5個節點，可以使用5x5的陣列儲存下圖。
若有邊相連，則陣列元素值改為邊的權重，否則陣列元素值改為0，因為是有向圖所以要注意起點與終點，將邊的權重加入正確的格子內。
使用陣列建立圖形資料結構範例程式，如下。
(二)使用deque陣列建立圖形資料結構
若使用deque所建立陣列進行儲存圖形資料結構，圖形資料結構的結構宣告如下。
宣告一個結構Edge，由3個元素描述一個邊，這個邊是具有方向性的，分別是from、to與w，from紀錄邊的起點，to紀錄邊的終點，w表示邊的權重，再宣告一個deque陣列用於記錄每個點可以連出去的所有邊，如此就可以將圖形以deque陣列表示。
若要將下圖使用deque陣列方式建立圖形資料結構，需不斷將邊加到指定的deque後面。
使用陣列G，將上圖所有點與邊加入後的結果如下，建立圖形後就可以使用各種圖形演算法，獲得想要的結果。
二、使用Dijkstra演算法找最短路徑
找出圖形中的最短路徑的演算法，常見的有三種，分別是Dijkstra演算法、BellmanFord演算法與Floyd演算法，以下分成三節進行介紹，每種演算法各有優缺點與適合的題目類型。
Dijkstra演算法是一種貪婪(Greedy)的演算法策略，最短路徑決定了就不能更改，不能用於邊的權重為負值的情形，只能找出單點對所有點的最短路徑，不能用於有負環的情形，所謂的負環就是形成循環(cycle)且循環的權重加總結果為負值，不斷的經過此循環就可以獲得更小的值，會造成無法在有限步驟中獲得最短路徑，所以Dijkstra演算法、BellmanFord演算法與Floyd演算法皆無法在有負環的圖中得到正確的最短路徑。
Dijkstra演算法
下圖以點0為出發點，找出到其他點的最短路徑。
(一)使用Dijkstra找最短路徑--節點從0編號
給定最多100個節點以內的無向圖，每個節點編號由0開始編號，且節點編號皆不相同，每個邊都有權重，且邊的權重為正整數，相同起點與終點的邊只有一個，求點0到所有其他點的最短路徑。
輸入說明
輸入正整數n與m，表示圖形中有n個點與m個邊，接下來有m行，每個邊輸入兩個節點編號與邊的權重，保證節點編號由0到(n-1)，邊的權重為正整數。
輸出說明
輸出點0到所有點的最短路徑。
範例輸入
6 9
0 1 6
0 2 5
0 3 11
0 4 16
1 2 3
2 3 2
2 5 10
3 4 2
3 5 3
範例輸出
0 6 5 7 9 10
(a)解題想法
使用陣列v紀錄是否已經獲得點0連到該點的最短路徑，預設值為0，設定為1表示該點已經確定最短路徑值，若陣列v元素為1，則該點就不會再找尋是否有更短路徑。陣列dis紀錄從點0到所有節點的最短路徑，預設為很大的數字，若有更短路徑就更新。使用優先權佇列(priority queue)每次找出從點0可以連結出去的點中最短路徑的點編號，設定該點的陣列v的值為1，表示該點已經確定最短路徑，更新該點能連出去到其他點的最短路徑到陣列dis，將這些點加入優先權佇列，優先權佇列在加入的過程中，會將點0到該點的權重較小的元素調整到最前面，每次都會取出權重最小的元素，如此不斷重複上述動作直到優先權佇列(priority queue)沒有元素為止，就可以找出所有點的最短路徑。
(b)程式碼
(c)程式結果預覽
按下「執行->編譯並執行」，結果顯示在螢幕如下。
(二)封包傳遞
網路傳輸的最小單位為封包，給定最多1000個節點以內的無向圖，每個節點表示一個網路設備，每個節點編號由0開始編號，且節點編號皆不相同，每個邊都有權重，且邊的權重為正整數，權重表示封包在兩個網路設備之間傳送所需要的時間，單位為毫秒，相同起點與終點的邊只有一個，求指定的點s(s由使用者輸入)是否有無法到達的點，請列出無法到達的點。
輸入說明
輸入正整數n、m與整數s，表示圖形中有n個點與m個邊，由點s出發找尋是否有無法到達的點，接下來有m行，每個邊輸入兩個節點編號與邊的權重，保證節點編號由0到(n-1)，邊的權重為正整數。
輸出說明
輸出點s無法到達的點。
範例輸入
6 7 1
0 1 6
0 2 5
0 3 11
0 4 16
1 2 3
2 3 2
3 4 2
範例輸出
點5無法到達
(a)解題想法
本題與練習題13-2-1解題想法相同，使用Dijkstra演算法找最短路徑解題，需要判斷是否無法到達，當完成最短路徑找尋後，陣列dis的元素數值還是初始值0x6f6f6f6f，表示該點是無法到達的點，輸出該點為無法到達即可。
(b)程式碼
(c)程式結果預覽
按下「執行->編譯並執行」，結果顯示在螢幕如下。
三、使用Bellman Ford演算法找最短路徑
Bellman Ford演算法是一種動態規劃(Dynamic Programming)的演算法策略，最短路徑決定了還可以更改，可以用於邊的權重為負值的情形，只能找出單點對所有點的最短路徑，不能用於負環的圖形上找尋最短路徑，但可以用於偵測圖形中是否有負環存在。
Bellman Ford演算法
下圖為有向圖，以點Ax為出發點，使用Bellman Ford演算法找出到其他點的最短路徑，宣告佇列qu紀錄新增找出最短路徑的點，陣列dis記錄從Ax出發到其他點的最短路徑，陣列inqu紀錄是否加入佇列中，已經在佇列中設定為1，從佇列取出設定為0。
(一)使用Bellman Ford找最短路徑
給定最多100個節點以內的有向圖，每個節點名稱由字串組成，且節點名稱皆不相同，每個邊都有權重，且邊的權重為整數，相同起點與終點且方向相同的邊只有一個，保證圖中不含負環，由指定的節點名稱為起點，到所有其他點的最短路徑。
輸入說明
輸入正整數n與m，表示圖形中有n個點與m個邊，接下來有m行，每行輸入兩個節點名稱與邊的權重，邊的權重為整數，最後輸入起點的節點名稱。
輸出說明
輸出指定節點到所有點的最短路徑。
範例輸入
5 7
Ax Bx 6
Ax Cx 5
Ax Dx 11
Ax Ex 16
Bx Cx -3
Cx Dx -2
Dx Ex 2
Ax
範例輸出
0 6 3 1 3
(a)解題想法
因為有權重為負的邊，且不含負環，所以使用Bellman Ford演算法找最短路徑解題，使用map將節點名稱轉成節點編號，才有辦法建立圖形，並任意指定最短路徑的起始節點。利用佇列版本的BellmanFord演算法解題，Bellman Ford演算法使用陣列dis紀錄從指定的起點到其他點的最短距離，使用佇列qu記錄可以產生更短距離的節點編號，使用陣列inqu紀錄該點是否已經加入佇列，避免重複加入佇列，每當有更短路徑且該點未加入佇列，則將該點加入佇列，每次從佇列取出一個元素，設定陣列inqu該點的狀態為已經從佇列取出，檢查該點可以連出去的邊是否有更短路徑存在，若有更短路徑存在，則更新最短路徑陣列dis，若該點未加入佇列，則加入佇列，設定陣列inqu為已經加入佇列，如此直到佇列為空就完成起點到所有點的最短距離，最短距離儲存在陣列dis，到此完成Bellman Ford演算法。
(b)程式碼
(c)程式結果預覽
按下「執行->編譯並執行」，結果顯示在螢幕如下。
(二)使用BellmanFord偵測負環
給定最多100個節點以內的有向圖，每個節點名稱由字串組成，且節點名稱皆不相同，每個邊都有權重，且邊的權重為整數，相同起點與終點且方向相同的邊只有一個，找出圖中是否含有負環。
輸入說明
輸入正整數n與m，表示圖形中有n個點與m個邊，接下來有m行，每行輸入兩個節點名稱與邊的權重，邊的權重為整數。
輸出說明
若有負環，則輸出「找到負環」，否則輸出「找不到負環」。
範例輸入
5 7
Ax Bx 6
Ax Ex 16
Bx Cx -3
Cx Ax 5
Cx Dx -2
Dx Ax -2
Dx Ex 2
範例輸出
找到負環
(a)解題想法
因為有權重為負的邊，偵測是否含負環，所以使用Bellman Ford演算法找最短路徑解題，增加一個陣列cnt記錄每個點找到更短路徑的次數，若大於等於n(n為圖中點的個數)，則表示圖中含有負環，其餘與前節13-3-1使用Bellman Ford演算法找最短路徑相同。
(b)程式碼
(d)程式結果預覽
按下「執行->編譯並執行」，結果顯示在螢幕如下。
四、使用Floyd Warshall演算法找最短路徑
Floyd Warshall演算法是一種動態規劃(Dynamic Programming)的演算法策略，最短路徑決定了還可以更改，可以用於邊的權重為負值的情形，可以找出所有點對所有點的最短路徑，但不能用於負環的圖形上找尋最短路徑。
下圖為有向圖，以點Ax為出發點，使用Floyd Warshall演算法找出到其他點的最短路徑，使用二維陣列dis紀錄每個點到另一個點的最短距離。
(一)使用FordWarshall找最短路徑
給定最多100個節點以內的有向圖，每個節點名稱由字串組成，且節點名稱皆不相同，每個邊都有權重，且邊的權重為整數，相同起點與終點且方向相同的邊只有一個，保證圖中不含負環，求所有點到其他點的最短路徑。
輸入說明
輸入正整數n與m，表示圖形中有n個點與m個邊，接下來有m行，每行輸入兩個節點名稱與邊的權重，邊的權重為整數。
輸出說明
考慮通過不同的節點，輸出所有點到其他點的最短路徑。
範例輸入
5 7
Ax Bx 6
Ax Cx 5
Ax Dx 11
Ax Ex 16
Bx Cx -3
Cx Dx -2
Dx Ex 2
範例輸出
0 6 5 11 16
INF 0 -3 INF INF
INF INF 0 -2 INF
INF INF INF 0 2
INF INF INF INF 0
0 6 3 11 16
INF 0 -3 INF INF
INF INF 0 -2 INF
INF INF INF 0 2
INF INF INF INF 0
0 6 3 1 16
INF 0 -3 -5 INF
INF INF 0 -2 INF
INF INF INF 0 2
INF INF INF INF 0
0 6 3 1 3
INF 0 -3 -5 -3
INF INF 0 -2 0
INF INF INF 0 2
INF INF INF INF 0
0 6 3 1 3
INF 0 -3 -5 -3
INF INF 0 -2 0
INF INF INF 0 2
INF INF INF INF 0
(a)解題想法
因為邊的權重可以是負的，且不含負環，要求所有點到其他點的最短路徑，所以使用Floyd Warshall演算法找最短路徑，使用map將節點名稱轉成節點編號，才有辦法建立圖形，使用三層迴圈找出所有點到其他點的最短路徑。
(b)程式碼
(c)程式結果預覽
按下「執行->編譯並執行」，結果顯示在螢幕如下。
(二)哪條路可以容納最多車子的數量
給定最多100個節點以內的無向圖，每個節點由編號命名，且節點編號皆不相同，每個邊都有權重，且邊的權重為正整數，表示該道路可以容納最多的車子有多少，相同起點與終點的邊只有一個，求所有點到其他點的可容納最多車子的數量。
輸入說明
輸入正整數n與m，表示圖形中有n個點與m個邊，接下來有m行，每行輸入兩個節點編號與邊的權重，邊的權重為正整數。
輸出說明
顯示所有點到其他點的可容納最多車子的數量。
範例輸入
5 7
0 1 6
0 2 5
0 3 11
0 4 16
1 2 3
2 3 2
3 4 2
範例輸出
0 6 5 11 16
6 0 5 6 6
5 5 0 5 5
11 6 5 0 11
16 6 5 11 0
(a)解題想法
(b)程式碼
(c)程式結果預覽
按下「執行->編譯並執行」，結果顯示在螢幕如下。
Page updated
Google Sites
Report abuse