離散數學最短路徑算法，python 圖論算法（一）

?????? 學習Python有一段時間了，看了幾本書，大部分時間都是拿它寫一些小的腳本，處理數據，最近用Python實現了幾個常見的圖論算法。第一部分就是圖的存儲和建立。

?????? 方法一，用矩陣存儲。所謂矩陣就是二維數組。Python的二維數組用起來更加隨意和簡單。寫了一個很low的控制臺輸入建立圖的方法。一時間也沒想起其他好的方法。

用二維數組存儲，對算法的實現很有幫助。

def buildgraph():n = input()m = input()inf = 100000graph = []for i in range(n):graph.append([])for j in range(n):if(i = j):graph[i].append(0)else:graph[i].append(inf)for k in range(m):a = input()b = input()w = input()graph[a][b] = graph[b][a] = wreturn graph  

先輸入節點數n，再輸入邊的數量m。注意我們建立的是無向圖。然后先構建一個N x N的二維數組并且全部賦值為inf。意為邊的大小都是無限大。接下來輸入m條邊，邊的表示用a b w 表示（a,b）為起點，w為權重。

離散數學最短路徑算法、

第二種方法，用邊級的形式。

edge = [[1,2,1],[1,2,3],[1,3,2],[2,3,1],[2,4,4],[3,4,2]]  

就不寫構建方法。