Embedded Files
圖形資料結構是由點與邊所組成，圖形資料結構廣泛應用於解決問題，例如：使用地圖搜尋最短路徑，將地點轉換成圖形資料結構中的點，地點與地點間的距離轉換成邊的權重，最後使用最短路徑演算法就可以找出最短路徑，如下圖。
11-1 實作圖形資料結構—新增邊的權重
實作邊帶有權重的圖形資料結構，接著介紹圖形資料結構的最短路徑演算法，如何利用程式找出起點到每個節點的最短路徑。
11-1-1使用陣列建立帶有權重的圖形資料結構
可以使用陣列建立圖形資料結構，如下圖形資料結構範例，本範例圖形結構有5個節點，可以使用5x5的陣列儲存下圖。
若有邊相連，則陣列元素值改為邊的權重，否則陣列元素值改為0。由下表可知無向圖一定是對稱陣列，因為點x可以連到點y，點y一定可以連回點x。
有向圖也可以使用陣列建立圖形資料結構，如下圖形資料結構範例，本範例圖形結構有5個節點，可以使用5x5的陣列儲存下圖。
若有邊相連，則陣列元素值改為邊的權重，否則陣列元素值改為0，因為是有向圖所以要注意起點與終點，將邊的權重加入正確的格子內。
以下為使用陣列建立邊帶有權重的圖形資料結構程式範例。
(11-1-1使用陣列建立帶有權重的圖形資料結構.py)
第1行：宣告陣列G為二維整數陣列，有100列與100行的元素。
第2行：輸入一個整數，變數n參考到此整數，表示有幾個邊要輸入。
第3到8行：使用迴圈執行n次，每次輸入兩個數字表示邊的兩個頂點到變數a與b，邊的權重到變數w(第4到7行)。設定G[a][b]為w，表示點a可以到點b，且權重為w(第8行)，設定G[b][a]為w，表示點b可以到點a，且權重為w(第9行)。
11-1-2使用字典建立帶有權重的圖形資料結構
若使用字典儲存帶有權重的圖形資料結構，因為需要儲存起始節點、終點節點與權重，宣告類別Edge如下。
class Edge:
def __init__(self, s, t, w):
self.s = s
self.t = t
self.w = w
宣告一個類別Edge，由3個元素描述一個邊，這個邊是具有方向性的，分別是s、t與w，s為邊的起始節點，t為邊的終點節點，w為邊的權重。若要將下圖使用字典建立圖形資料結構，需不斷將邊加到指定的字典元素後面。
使用陣列G，將上圖所有點與邊加入後的結果如下，建立圖形後就可以使用各種圖形演算法，獲得想要的結果。
(11-1-2使用字典建立帶有權重的圖形資料結構.py)
第1到5行：宣告一個Edge類別，由3個元素描述一個邊，這個邊是具有方向性的，分別是s、t與w，s為邊的起點，t為邊的終點，w為邊的權重。
第6行：宣告G為空字典。
第7行：使用input函數輸入一個整數到變數n，使用int函式將整數字串轉換成整數，表示有幾個邊要輸入。
第8到22行：使用迴圈執行n次，每次輸入3個數字表示邊的兩個頂點到變數a與b，與邊的權重到變數w(第9到12行)。設定物件e1的s為a、物件e1的t為b，物件e1的w為w(第13行)，設定物件e2的s為b、物件e2的t為a，物件e2的w為w(第14行)。如果字典G包含鍵值a，則將e1加入到G[a]的最後，表示點a可以到點b，且權重為w (第15到16行)，否則建立新的鍵值a對應到串列，該串列有一個元素e1，表示點a可以到點b，且權重為w(第17到18行)。如果字典G包含鍵值b，將e2加入到G[b]的最後，表示點b可以到點a，且權重為w (第19到20行)，否則建立新的鍵值b對應到串列，該串列有一個元素e2，表示點b可以到點a，且權重為w (第21到22行)。
11-2使用Dijkstra演算法找最短路徑
找出圖形中的最短路徑的演算法，常見的有三種，分別是Dijkstra演算法、BellmanFord演算法與Floyd演算法，以下分成三節進行介紹，每種演算法各有優缺點。
Dijkstra演算法是一種貪婪(Greedy)的演算法策略，最短路徑決定了就不能更改，不能用於邊的權重為負值的情形，只能找出單點對所有點的最短路徑，不能用於有負環的情形，所謂的負環就是最短路徑形成循環(cycle)且循環的權重加總結果為負值，不斷的經過此循環就可以獲得更小的值，會造成無法在有限步驟中獲得最短路徑，Dijkstra演算法、BellmanFord演算法與Floyd演算法皆無法在有負環的圖中得到正確的最短路徑。
Dijkstra演算法
11-2-1-使用Dijkstra找最短路徑
給定最多100個節點以內的無向圖，每個節點名稱由字串組成，且節點名稱皆不相同，每個邊都有權重，且邊的權重為正整數，相同起點與終點的邊只有一個，由指定的節點名稱為起點，到所有其他點的最短路徑。假設任兩點的路徑長度不會超過500000。
輸入說明
輸入正整數m，表示圖形中有m個邊，接下來有m行，每行輸入兩個節點名稱與邊的權重，邊的權重為正整數，最後輸入指定為起點的節點名稱。
輸出說明
輸出指定節點到所有點的最短路徑。
範例輸出
0 6 5 7 9 10
使用Dijkstra演算法找最短路徑的程式實作想法
首先使用字典將節點名稱轉成節點編號(從0開始編號)，再使用節點編號透過另一個字典建立圖形資料結構。使用Dijkstra演算法找最短路徑，使用陣列v紀錄是否已經獲得出發點連到該點的最短路徑，預設為0，設定為1時，表示該點已經確定最短路徑的距離，該點就不會再找尋是否有更短路徑。
陣列dis紀錄從開始點到所有節點的最短路徑，預設為很大的數字，若有更短路徑就更新。使用優先權佇列(priority queue)每次找出從出發點可以連結出去的點中最短路徑的點編號，假如該點的陣列v的值等於0，則設定該點的陣列v的值為1，表示該點已經確定最短路徑，更新該點能連出去到其他點的最短路徑的距離到陣列dis，將這些點加入優先權佇列，優先權佇列在加入的過程中，會將出發點到該點的權重較小的元素調整到最前面，每次都會取出權重最小的元素，如此不斷重複上述動作直到優先權佇列(priority queue)沒有元素為止，就可以找出所有點的最短路徑。
本範例程式使用Python的優先權佇列函式庫heapq，以下為函式庫heapq的常用函式，使用「heapq.heappush((heap, item)」將元素加入堆積(Heap)，使用「heapq.heappop(heap)」從堆積將元素取出。
(一) 將元素加入堆積
函式heappush
（說明文件：https://docs.python.org/zhtw/3/library/heapq.html#heapq.heappush）
【函式簽名】heapq.heappush(heap, item)
【功能與說明】將元素item加入到堆積heap內，item可以是數值或tuple，tuple的第一個參數進行數值比較，數值小的在前面。
【程式範例1 - 堆積內每一個元素為整數】
import heapq
nums = [8,5,3,4,6,2]
pq = []
for i in nums:
heapq.heappush(pq, i)
print(pq)
【執行結果1】
[8]
[5, 8]
[3, 8, 5]
[3, 4, 5, 8]
[3, 4, 5, 8, 6]
[2, 4, 3, 8, 6, 5]
【程式範例2 - 堆積內每一個元素為tuple】
import heapq
data = [(8,'a'),(5,'x'),(3,'b')]
pq = []
for i in data:
heapq.heappush(pq, i)
print(pq)
【執行結果2】
[(8, 'a')]
[(5, 'x'), (8, 'a')]
[(3, 'b'), (8, 'a'), (5, 'x')]
(二)從堆積取出元素
函式heappop
（說明文件：https://docs.python.org/zhtw/3/library/heapq.html#heapq.heappop）
【函式簽名】heapq.heappop(heap)
【功能與說明】從堆積heap取出最上面的元素回傳回來。
【程式範例】
import heapq
nums = [8,5,3,4,6,2]
pq = []
for i in nums:
heapq.heappush(pq, i)
while len(pq) > 0:
print(heapq.heappop(pq)," ",sep="",end="")
print()
【執行結果】
2 3 4 5 6 8
(11-2-1使用Dijkstra找最短路徑.py)
第1行：匯入heapq函式庫。
第2到3行：宣告City與G為空字典。
第4行：宣告pq為串列。
第5行：宣告dis為101個元素的串列，每個元素值都是1000000。
第5行：宣告v為101個元素的串列，每個元素值都是0。
第7到10行：定義getCityIndex函式，將節點名稱轉成數字，使用字串p為輸入，將節點名稱p轉換成節點編號。若p不是字典City的鍵值，則設定City[p]，所對應的值為字典City的長度(第8到9行)。回傳字典City以p為鍵值的對應值(第10行)。
第11到15行：宣告一個Edge類別，由3個元素描述一個邊，這個邊是具有方向性的，分別是s、t與w，s為邊的起點，t為邊的終點，w為邊的權重。
第17行：使用input函數輸入一個整數到變數n，使用int函式將整數字串轉換成整數，表示有幾個邊要輸入。
第18到32行：使用迴圈執行n次，每次輸入3個資料，表示邊的兩個頂點到變數a與b，與邊的權重到變數w(第19到22行)。設定物件e1的s為a、物件e1的t為b，物件e1的w為w(第23行)，設定物件e2的s為b、物件e2的t為a，物件e2的w為w(第24行)。如果字典G包含鍵值a，則將e1加入到G[a]的最後，表示點a可以到點b，且權重為w (第25到26行)，否則建立新的鍵值a對應到串列，該串列有一個元素e1，表示點a可以到點b，且權重為w(第27到28行)。如果字典G包含鍵值b，將e2加入到G[b]的最後，表示點b可以到點a，且權重為w (第29到30行)，否則建立新的鍵值b對應到串列，該串列有一個元素e2，表示點b可以到點a，且權重為w (第31到32行)。
第34行：使用函式input輸入起點節點名稱，傳入函式getCityIndex轉換成節點編號，變數s參考到此節點編號。
第35行：建立有兩個元素的tuple，第一個元素表示距離，起始點的距離為0，第二個元素表示目標點編號，起始點編號為變數s，變數p參考到此tuple。
第36行：將變數p加入到串列pq，串列pq經由函式heappush轉換成優先權佇列(priority queue)，每個元素為「距離」與「目標點編號」的tuple，函式heappush會自動將距離小的元素調整到上層，形成MinHeap。
第37行：設定dis[s]為0，表示出發點(點s)的最短距離為0。
第38到48行：實作Dijkstra演算法程式，當pq不是空的，執行以下動作。
第39行：使用函式heappop從pq取出最上面的元素(起始點到此點是最短距離)，變數p參考到此元素。
第40行：宣告變數s參考到變數p的第2個元素，為該邊的目標點編號，會是下一個起點。
第41到48行：若陣列v[s]等於0，設定v[s]為1，表示起始點到節點編號s是最短路徑。
第43到48行：使用迴圈找出從點s可以連出去的所有邊到變數edge，若v[edge.t]等於0，表示點edge.t還沒有確定從出發點(點s)連結到該點的最短路徑(第44行)，若dis[edge.t]大於(dis[s] + edge.w)，表示找到出發點(點s)到點edge.t的更短路徑，則設定dis[edge.t]為(dis[s] + edge.w) (第46行)，建立兩個元素的tuple，第一個元素為dis[edge.t]，表示起始點到目標點edge.t的距離，第二個元素為edge.t (第47行)，表示目標點編號，變數p參考到此tuple，將變數p加入到pq(第48行)。
第49到50行：使用迴圈顯示陣列dis到螢幕。
第51行：輸出換行。
(b)程式執行結果
輸入以下測試資料。
9
Ax Bx 6
Ax Cx 5
Ax Dx 11
Ax Ex 16
Bx Cx 3
Cx Dx 2
Cx Fx 10
Dx Ex 2
Dx Fx 3
Ax
執行結果顯示在螢幕如下。
0 6 5 7 9 10
(c)程式效率分析
執行第38到48行的演算法效率每個點連出去的邊最多拜訪兩次，演算法效率為O(n+m)，n為點的個數，m為邊的個數。將一個元素加入優先權佇列與從優先權佇列取出元素的程式效率為O(log(n))，n為優先權佇列的元素個數，n可以使用圖中節點個數取代，所有點加入優先權佇列與從優先權佇列取出的效率為O(n*log(n))，整個程式效率為O(m+n*log(n))。
11-3使用Bellman Ford演算法找最短路徑
Bellman Ford演算法是一種動態規劃(Dynamic Programming)的演算法策略，最短路徑決定了還可以更改，可以用於邊的權重為負值的情形，只能找出單點對所有點的最短路徑，不能用於負環的圖形上找尋最短路徑，但可以用於偵測圖形中是否有負環存在。
Bellman Ford演算法
下圖為有向圖，以點Ax為出發點，使用Bellman Ford演算法找出到其他點的最短路徑，宣告佇列qu紀錄新增找出最短路徑的點，陣列dis記錄從Ax出發到其他點的最短路徑，陣列inqu紀錄是否加入佇列中，已經在佇列中設定為1，從佇列取出設定為0。
點Ax的節點編號為0，點Bx的節點編號為1，點Cx的節點編號為2，點Dx的節點編號為3，點Ex的節點編號為4。使用一個陣列dis暫存由點Ax連接出去的各點最短路徑，初始化點Ax為0，其他點為無限大，將點Ax加入佇列qu，設定陣列inqu表示點Ax的元素為1，其他點為0，表示點Ax在佇列qu中。
Step1)從佇列qu取出最前面的元素點Ax，設定陣列inqu中表示點Ax的元素值為0，表示點Ax不在佇列內。從點Ax可以連出去的點Bx、點Cx、點Dx與點Ex，更新這些點的最短路徑陣列dis的元素值。檢查點Bx、點Cx、點Dx與點Ex的陣列inqu的元素值是否為0，若是0，則將這些點加入佇列qu，設定對應的陣列inqu元素為1，表示這些點加入佇列qu中。
Step2)從佇列qu取出最前面的元素點Bx，設定陣列inqu中表示點Bx的元素值為0，表示點Bx不在佇列內。從點Bx可以連出去的點Cx，是否有更短距離到達點Cx，發現有更短距離，更新點Cx的最短路徑陣列dis的元素值。檢查點Cx的陣列inqu的元素值是否為0，發現是1，已經在佇列qu中，則不加入佇列qu。
Step3)從佇列qu取出最前面的元素點Cx，設定陣列inqu中表示點Cx的元素值為0，表示點Cx不在佇列內。從點Cx可以連出去的點Dx，是否有更短距離到達點Dx，發現有更短距離，更新點Dx的最短路徑陣列dis的元素值。檢查點Dx的陣列inqu的元素值是否為0，發現是1，已經在佇列qu中，則不加入佇列qu。
Step4)從佇列qu取出最前面的元素點Dx，設定陣列inqu中表示點Dx的元素值為0，表示點Dx不在佇列內。從點Dx可以連出去的點Ex，是否有更短距離到達點Ex，發現有更短距離，更新點Ex的最短路徑陣列dis的元素值。檢查點Ex的陣列inqu的元素值是否為0，發現是1，已經在佇列qu中，則不加入佇列qu。
Step5)從佇列qu取出最前面的元素點Ex，設定陣列inqu中表示點Ex的元素值為0，表示點Ex不在佇列內。從點Ex沒有可以連出去的點，沒有更短的路徑可以到其他點。
Step6)佇列qu是空的，Bellman Ford演算法到此結束。
11-3-1-使用Bellman Ford找最短路徑
給定最多100個節點以內的有向圖，每個節點名稱由字串組成，且節點名稱皆不相同，每個邊都有權重，且邊的權重為整數，相同起點與終點且方向相同的邊只有一個，保證圖中不含負環，由指定的節點名稱為起點，到所有其他點的最短路徑。假設任兩點的路徑長度不會超過500000。
輸入說明
輸入正整數m，表示圖形中有m個邊，接下來有m行，每行輸入兩個節點名稱與邊的權重，邊的權重為整數，最後輸入起點的節點名稱。
輸出說明
輸出指定節點到所有點的最短路徑。
範例輸入
範例輸出
0 6 3 1 3
使用Bellman Ford演算法找出最短路徑的程式實作想法
因為有權重為負的邊，且不含負環，所以使用Bellman Ford演算法找最短路徑，使用字典將節點名稱轉成節點編號，建立圖形資料結構。利用佇列版本的BellmanFord演算法解題，Bellman Ford演算法使用陣列dis紀錄從指定的起點到其他點的最短距離，使用佇列qu記錄可以產生更短距離的節點編號。使用陣列inqu紀錄該點是否已經加入佇列，避免重複加入佇列，每當有更短路徑且該點未加入佇列，則將該點加入佇列，每次從佇列取出一個元素，設定陣列inqu該點的狀態為已經從佇列取出。檢查該點可以連出去的邊是否有更短路徑存在，若有更短路徑存在，則更新最短路徑陣列dis，若該點未加入佇列，則加入佇列，設定陣列inqu為已經加入佇列。直到佇列為空就完成起點到所有點的最短距離，最短距離儲存在陣列dis，到此完成Bellman Ford演算法。
(a)程式碼與解說
(11-3-1-使用BellmanFord找最短路徑.py)
第1到2行：宣告City與G為空字典。
第3行：宣告qu為串列。
第4行：宣告dis為101個元素的串列，每個元素值都是1000000。
第5行：宣告inqu為101個元素的串列，每個元素值都是0。
第6到9行：定義getCityIndex函式，將節點名稱轉成數字，使用字串p為輸入參數，將節點名稱p轉換成節點編號。若p不是字典City的鍵值，則設定City[p]，所對應的值為字典City的長度(第7到8行)。回傳字典City以p為鍵值的對應值(第9行)。
第10到14：宣告一個Edge類別，由3個元素描述一個邊，這個邊是具有方向性的，分別是s、t與w，s為邊的起點，t為邊的終點，w為邊的權重。
第15：使用input函數輸入一個整數到變數m，使用int函式將整數字串轉換成整數，表示有幾個邊要輸入。
第16到25行：使用迴圈執行m次，每次輸入3個資料，表示邊的兩個頂點到變數a與b，與邊的權重到變數w(第17到20行)。設定物件e1的s為a、物件e1的t為b，物件e1的w為w(第21行)。如果字典G包含鍵值a，則將e1加入到G[a]的最後，表示點a可以到點b (第22到23行)，否則建立新的鍵值a對應到串列，該串列有一個元素e1，表示點a可以到點b(第24到25行)。
第26行：使用函式input輸入起點節點名稱，傳入函式getCityIndex轉換成節點編號，變數s參考到此節點編號。
第27行：將變數s加入到串列qu。
第28行：設定dis[s]為0，表示出發點(點s)的最短距離為0。
第29行：設定inqu[s]為1，表示變數s所表示的節點，已經在佇列qu內。
第30到39行：實作Bellman Ford 演算法程式，當qu不是空的，執行以下動作。
第31行：從qu取出最前面的元素儲存到變數p，並刪除qu最前面的元素。
第32行：設定inqu[p]為0，表示節點編號p的點已經從佇列qu取出。
第33行到39行：若字典G內有節點編號p，則使用迴圈找出從節點編號p可以連出去的所有邊(第34行)，若dis[edge.t]大於(dis[edge.s] + edge.w)，表示找到出發點s到節點編號edge.t的更短路徑，則設定dis[edge.t]為dis[edge.s] + edge.w (第35到36行)。若inqu[edge.t]等於0，表示點edge.t還沒加入佇列qu，則將edge.t加入到佇列qu，設定inqu[edge.t]為1，表示節點編號edge.t已經加入佇列qu(第37到39行)。
第40到41行：使用迴圈顯示陣列dis到螢幕上。
第42行：輸出換行。
(b)程式執行結果
輸入以下測試資料。
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
(c)程式效率分析
執行第30到39行的Bellman Ford演算法，每個點都可以加入佇列，點取出後可慮可以連出去的邊，所以演算法效率最差為O(n*m)，n為圖形中點的個數，m為圖形中邊的個數。
11-3-2-使用BellmanFord偵測負環
給定最多100個節點以內的有向圖，每個節點名稱由字串組成，且節點名稱皆不相同，每個邊都有權重，且邊的權重為整數，相同起點與終點且方向相同的邊只有一個，找出圖形是否包含負環。假設任兩點的路徑長度不會超過500000。
輸入說明
輸入正整數m，表示圖形中有m個邊，接下來有m行，每行輸入兩個節點名稱與邊的權重，邊的權重為整數。
輸出說明
若有負環，則輸出「找到負環」，否則輸出「找不到負環」。
範例輸入
範例輸出
找到負環
使用Bellman Ford找出負環
因為有權重為負的邊，偵測是否含負環，所以使用Bellman Ford演算法找最短路徑解題，增加一個陣列cnt記錄每個點找到更短路徑的次數，若大於等於n(n為圖中點的個數)，則表示圖中含有負環，其餘與前節11-3-1使用Bellman Ford演算法找最短路徑相同。
(a)程式碼與解說
(11-3-2-使用BellmanFord偵測負環.py)
第1到2行：宣告City與G為空字典。
第3到6行：定義getCityIndex函式，將節點名稱轉成數字，使用字串p為輸入參數，將節點名稱p轉換成節點編號。若p不是字典City的鍵值，則設定City[p]，所對應的值為字典City的長度(第4到5行)。回傳字典City以p為鍵值的對應值(第6行)。
第7到11行：宣告一個Edge類別，由3個元素描述一個邊，這個邊是具有方向性的，分別是s、t與w，s為邊的起點，t為邊的終點，w為邊的權重。
第12行：使用input函數輸入一個整數到變數m，使用int函式將整數字串轉換成整數，表示有幾個邊要輸入。
第13到23行：使用迴圈執行m次，每次輸入3個資料，表示邊的兩個頂點到變數a與b，與邊的權重到變數w(第14到17行)。設定物件e1的s為a、物件e1的t為b，物件e1的w為w(第18行)。如果字典G包含鍵值a，則將e1加入到G[a]的最後，表示點a可以到點b，且權重為w (第19到20行)，否則建立新的鍵值a對應到串列，該串列有一個元素e1，表示點a可以到點b，且權重為w (第21到22行)。
第23到44行：定義函式BellmanFord，以起始點s為輸入參數，如果找到負環，回傳True，否則回傳False。
第24行：宣告qu為串列。
第25行：宣告dis為101個元素的串列，每個元素值都是1000000。
第26行：宣告inqu為101個元素的串列，每個元素值都是0。
第27行：宣告cnt為101個元素的串列，每個元素值都是0。
第28行：將變數s加入到串列qu。
第29行：設定dis[s]為0，表示出發點(點s)的最短距離為0。
第30行：設定inqu[s]為1，表示變數s所表示的節點，已經在佇列qu內。
第31到43行：實作Bellman Ford 演算法程式，當qu不是空的，執行以下動作。
第32行：從qu取出最前面的元素儲存到變數p，並刪除qu最前面的元素。
第33行：設定inqu[p]為0，表示節點編號p的點已經從佇列qu取出。
第34到43行：若字典G內有節點編號p，有可以連出去的點(第34行)，則使用迴圈找出從節點編號p可以連出去的所有邊(第35行)，若dis[edge.t]大於(dis[edge.s] + edge.w)，表示找到出發點s到節點編號edge.t的更短路徑，則設定dis[edge.t]為dis[edge.s] + edge.w，cnt[edge.t]遞增1，表示節點edge.t更新增加1次(第36到38行)。若cnt[edge.t]大於len(City)，更新次數超過圖形內點的個數，則回傳True(第39到40行)。若inqu[edge.t]等於0，表示點edge.t還沒加入佇列qu，則將edge.t加入到佇列qu，設定inqu[edge.t]為1，表示節點編號edge.t已經加入佇列qu(第41到43行)。
第44行：若更新沒有超過n次，則回傳False。
第45行：設定變數ans為False。
第46到49行：使用迴圈執行BellmanFord函式，迴圈變數i，由0到字典City長度減1，每次遞增1，呼叫BellmanFord函式，以i為參數傳入，回傳結果儲存到變數ans(第47行)。若ans為true，表示找到負環，就中斷迴圈(第48到49行)。
第50到53行：若ans為true，則顯示「找到負環」，否則顯示「找不到負環」。
(b)程式執行結果
輸入以下測試資料。
7
Ax Bx 6
Ax Ex 16
Bx Cx -3
Cx Ax 5
Cx Dx -2
Dx Ax -2
Dx Ex 2
執行結果顯示在螢幕如下。
找到負環
(c)程式效率分析
執行第23到44行的Bellman Ford演算法，每個點都可以加入佇列，點取出後可慮可以連出去的邊，所以演算法效率最差為O(n*m)，n為圖形中點的個數，m為圖形中邊的個數。執行第46到49行，每一個節點都要執行Bellman Ford演算法，所以整個演算法效率為O(n^2*m)
11-4使用Floyd Warshall演算法找最短路徑
Floyd Warshall演算法是一種動態規劃(Dynamic Programming)的演算法策略，最短路徑決定了還可以更改，可以用於邊的權重為負值的情形，可以找出所有點對所有點的最短路徑，但不能用於負環的圖形上找尋最短路徑，也可以用於偵測負環，只要計算結果從i點出發回到點i的最短路徑數值小於0(也就是dis[i][i]<0，二維陣列dis定義如下方Floyd Warshall演算法)，就形成負環。
Floyd Warshall演算法
下圖為有向圖，使用Floyd Warshall演算法找出所有點的最短路徑，使用二維陣列dis紀錄每個點到另一個點的最短距離，Ax轉換成節點編號0，Bx轉換成節點編號1，Cx轉換成節點編號2，Dx轉換成節點編號3，Ex轉換成節點編號4。
11-4-1-使用FordWarshall找最短路徑
給定最多100個節點以內的有向圖，每個節點名稱由字串組成，且節點名稱皆不相同，每個邊都有權重，且邊的權重為整數，可以是負數，相同起點與終點且方向相同的邊只有一個，保證圖中不含負環，求所有點到其他點的最短路徑。
輸入說明
輸入正整數m，表示圖形中有m個邊，接下來有m行，每行輸入兩個節點名稱與邊的權重，邊的權重為整數。
輸出說明
輸出所有點到其他點的最短路徑。
範例輸入
範例輸出
只顯示最後結果。
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
使用Floyd Warshall演算法找最短路徑的程式實作想法
因為邊的權重可以是負的，且不含負環，要求所有點到其他點的最短路徑，所以使用Floyd Warshall演算法找最短路徑，使用字典將節點名稱轉成節點編號，接著建立圖形資料結構，使用三層迴圈找出所有點到其他點的最短路徑。
(a)程式碼與解說
(11-4-1-使用FordWarshall找最短路徑.py)
第1到2行：宣告City與G為空字典。
第3行：宣告dis為二維陣列，有100列100行，每個元素值都是1000000。
第4到7行：定義getCityIndex函式，將節點名稱轉成數字，使用字串p為輸入參數，將節點名稱p轉換成節點編號。若p不是字典City的鍵值，則設定City[p]所對應的值為字典City的長度(第5到6行)。回傳字典City以p為鍵值的對應值(第7行)。
第8行：使用input函數輸入一個整數到變數m，使用int函式將整數字串轉換成整數，表示有幾個邊要輸入。
第9到14行：使用迴圈執行m次，每次輸入3個資料，表示邊的兩個頂點到變數a與b，與邊的權重到變數w(第10到13行)。設定dis[a][b]為w，表示點a到點b的權重為w (第14行)。
第15到16行：設定二維陣列City的對角線元素為0。
第17到22行：此部分為Floyd Warshall演算法，使用三層巢狀迴圈，外層迴圈的迴圈變數為k，由0到(len(City)-1)，每次遞增1，第二層迴圈的迴圈變數為i，由0到(len(City)-1)，每次遞增1，內層迴圈的迴圈變數為j，由0到(len(City)-1)，每次遞增1，若(dis[i][k]等於1000000)或(dis[k][j]等於1000000)，就使用continue跳出內層迴圈，回到第二層迴圈繼續執行，取出dis[i][j]與dis[i][k]+dis[k][j]較小者設定給dis[i][j]。
第23到29行：當第二層迴圈執行完畢，就使用巢狀迴圈印出陣列dis目前的狀態。
(b)程式執行結果
輸入以下測試資料。
7
Ax Bx 6
Ax Cx 5
Ax Dx 11
Ax Ex 16
Bx Cx -3
Cx Dx -2
Dx Ex 2
執行結果顯示在螢幕如下。
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
(c)程式效率分析
執行第17到22行的Floyd Warshall演算法，使用三層迴圈，所以演算法效率為O(n^3)，n為圖形中點的個數。
Page updated
Google Sites
Report abuse