Floyd 算法
簡介
Floyd 算法又稱為插點法，是一種利用動態(tài)規(guī)劃的思想尋找給定的加權(quán)圖中多源點之間最短路徑的算法默责，與 Dijkstra 算法類似。
該算法名稱以創(chuàng)始人之一鲫懒、1978 年圖靈獎獲得者遭居、斯坦福大學(xué)計算機科學(xué)系教授羅伯特 · 弗洛伊德命名。
核心思路
路徑矩陣
- 通過一個圖的權(quán)值矩陣求出它的每兩點間的最短路徑矩陣玛追。
- 從圖的帶權(quán)鄰接矩陣 A=[a(i,j)] n×n 開始税课，遞歸地進行 n 次更新，即由矩陣 D(0)=A豹缀，按一個公式伯复，構(gòu)造出矩陣 D(1)；又用同樣地公式由 D(1) 構(gòu)造出 D(2)邢笙；……啸如；最后又用同樣的公式由 D(n-1) 構(gòu)造出矩陣 D(n)。矩陣 D(n) 的 i 行 j 列元素便是 i 號頂點到 j 號頂點的最短路徑長度氮惯，稱 D(n) 為圖的距離矩陣叮雳，同時還可引入一個后繼節(jié)點矩陣 path 來記錄兩點間的最短路徑。
- 采用松弛技術(shù)（松弛操作）妇汗，對在 i 和 j 之間的所有其他點進行一次松弛帘不。所以時間復(fù)雜度為 O(n^3)。
狀態(tài)轉(zhuǎn)移方程
path[i,j]:=min{path[i,k]+path[k,j],path[i,j]}
算法描述
從任意一條單邊路徑開始杨箭。所有兩點之間的距離是邊的權(quán)寞焙，如果兩點之間沒有邊相連，則權(quán)為無窮大互婿。
對于每一對頂點 u 和 v捣郊，看看是否存在一個頂點 w （一般稱為中間點）使得從 u 到 w 再到 v 比已知的路徑更短。如果是慈参，更新它（專業(yè)術(shù)語為：松弛）呛牲。
遍歷直到結(jié)束，這時候存儲圖的數(shù)據(jù)結(jié)構(gòu)就得到了多源最短路徑驮配。
優(yōu)缺點分析
-
Floyd 算法適用于 APSP(All Pairs Shortest Paths娘扩，多源最短路徑)着茸，是一種動態(tài)規(guī)劃算法，稠密圖效果最佳琐旁，邊權(quán)可正可負涮阔。此算法簡單有效，由于三重循環(huán)結(jié)構(gòu)緊湊旋膳，對于稠密圖澎语，效率要高于執(zhí)行 | V | 次 Dijkstra 算法，也要高于執(zhí)行 | V | 次 SPFA 算法验懊。
稠密圖定義：邊的條數(shù) | E | 接近 | V|2擅羞，稱為稠密圖（dense graph）
優(yōu)點：容易理解，可以算出任意兩個節(jié)點之間的最短距離义图，代碼編寫簡單减俏。
缺點：時間復(fù)雜度比較高，不適合計算大量數(shù)據(jù)娃承。時間復(fù)雜度 O（n^3）,空間復(fù)雜度 O（n^2）。
Python 代碼實現(xiàn)
-
代碼：
import copy M=1000000 def Floyd(G): n=len(G) path=copy.deepcopy(G) for k in range(0,n): for i in range(0,n): for j in range(0,n): print("Comparing path[%s][%s] and {path[%s][%s]+path[%s][%s]}"%(i,j,i,k,k,j)) print("Former path[%s][%s] = %s"%(i,j,path[i][j])) path[i][j]=min(path[i][j],path[i][k]+path[k][j]) print("Present path[%s][%s] = %s\n"%(i,j,path[i][j])) return path if __name__=='__main__': G=[ [0,30,15,M,M,M], [5,0,M,M,20,30], [M,10,0,M,M,15], [M,M,M,0,M,M], [M,M,M,10,0,M], [M,M,M,30,10,0] ] print("---------------Floyd----------------") path=Floyd(G) print("Graph = ") for i in range(0,len(G)): print (path[i])
代碼詳解
引入 copy 怕篷，定義無窮值历筝，在 Python 里還有種寫法：
M = float('inf')定義 Floyd 函數(shù)，參數(shù)為圖的鄰接矩陣 G廊谓，在里面首先利用 copy 函數(shù)復(fù)制一份梳猪，不復(fù)制的話，會導(dǎo)致兩個變量指向同一個地址（鄰接矩陣）
三重 for 循環(huán)蒸痹，很容易理解
-
if __name__=='__main__'不理解的復(fù)制這段代碼春弥，百度谷歌
測試
還是拿我的另一篇文章 Dijkstra 算法 中的測試用例
-
鄰接矩陣：
G=[ [0,30,15,M,M,M], [5,0,M,M,20,30], [M,10,0,M,M,15], [M,M,M,0,M,M], [M,M,M,10,0,M], [M,M,M,30,10,0] ] -
表示的圖如下：
test -
輸出：
floydtest
小結(jié)
從上面的輸出結(jié)果可以看到 G 矩陣已經(jīng)被更新了
有些走不通的路徑現(xiàn)在可以走通了，因為原來是鄰接矩陣：兩個頂點有鄰接邊叠荠，鄰接矩陣對應(yīng)點才有值匿沛；現(xiàn)在是整個網(wǎng)絡(luò)，頂點 i 到頂點 j 如果可達榛鼎，那么
G[i][j]就有值逃呼。但是，我們是得到了兩個點的最小 cost者娱，最短路徑要怎么得到呢蜘渣？可以再借助一個 path 矩陣，它記錄了中間點的信息肺然，我們可以在最后根據(jù)更新后的 G 矩陣回溯 path 矩陣得到最短路徑。
全局最短路徑的數(shù)據(jù)結(jié)構(gòu)
ShortestPath_dict = {
0: {1: [0, 2, 1], 2: [0, 2], 3: [0, 2, 5, 4, 3], 4: [0, 2, 5, 4], 5: [0, 2, 5]},
1: {0: [1, 0], 2: [1, 0, 2], 3: [1, 4, 3], 4: [1, 4], 5: [1, 5]}, 2: {0: [2, 1, 0],
1: [2, 1], 3: [2, 5, 4, 3], 4: [2, 5, 4], 5: [2, 5]},
3: {0: [], 1: [], 2: [], 4: [], 5: []},
4: {0: [], 1: [], 2: [], 3: [4, 3], 5: []},
5: {0: [], 1: [], 2: [], 3: [5, 4, 3], 4: [5, 4]}
}
- 這個數(shù)據(jù)結(jié)構(gòu)利用了字典與列表腿准，其中每兩個頂點的最短路徑用列表表示际起，如頂點 0 到頂點 1 ：
0: {1: [0, 2, 1]拾碌，其中的[0, 2, 1]就是最短路徑。
利用 Floyd 得到全局最短路徑
-
代碼：
# ------------------函數(shù)------------------- def back_path(path,i,j,shortestPath): #遞歸回溯 print ("path[%s][%s] = "%(i,j),path[i][j]) if -1 != path[i][j]: shortestPath = back_path(path,i,path[i][j],shortestPath) shortestPath = back_path(path,path[i][j],j,shortestPath) if j not in shortestPath: shortestPath.append(j) return shortestPath def getShortestPath(graph,path,i,j): shortestPath = [] if graph[i][j] == float('inf') or i == j: print("頂點%s 不能到達 頂點%s街望！"%(i,j)) return shortestPath elif path[i][j] == -1: shortestPath.append(i) shortestPath.append(j) else : shortestPath.append(i) shortestPath = back_path(path,i,j,shortestPath) print("頂點%s 到 頂點%s 的路徑為："%(i,j),shortestPath) return shortestPath def getAllShortestPath(graph,path): print("------正在生成全局最短路徑------") ShortestPath_dict = {} for i in range(N): ShortestPath_dict[i] = {} for j in range(N): print("嘗試生成頂點%s到頂點%s的最短路徑..."%(i,j)) if i !=j : shortestPath = getShortestPath(graph,path,i,j) ShortestPath_dict[i][j] = shortestPath print("--------------------------------") return ShortestPath_dict # ----------------------定義-------------------- M=float('inf') #無窮大 graph = [ [0,30,15,M,M,M], [5,0,M,M,20,30], [M,10,0,M,M,15], [M,M,M,0,M,M], [M,M,M,10,0,M], [M,M,M,30,10,0] ] N = len(graph) path = [] for i in range(N): path.append([]) for j in range(N): path[i].append(-1) print ("Original Graph:\n",graph) # -----------------Floyd Algorithm---------------- for k in range(N): for i in range(N): for j in range(N): if graph[i][j] > graph[i][k] + graph[k][j]: graph[i][j] = graph[i][k] + graph[k][j] path[i][j] = k print ("Shortest Graph:\n",graph) print ("Path:\n",path) print("ShortestPath =\n",getAllShortestPath(graph,path))
測試2
鄰接矩陣如上所示
表示的圖也如上所示
-
截圖
test3
last
代碼詳解2
在三重循環(huán)階段校翔，與前文第一種做法不同的是：每次還加入了
path[i][j] = k，這樣每次松弛灾前，都會被記錄在 path 矩陣中path 矩陣完成后防症，如測試2中的截圖所示
-
getAllShortestPath函數(shù)- 構(gòu)造字典 ShortestPath_dict
- 兩兩遍歷圖中各點，循環(huán)調(diào)用
getShortestPath函數(shù)
-
getShortestPath函數(shù)- 如果兩個頂點不可達或者這兩個頂點為同一個頂點哎甲，那么直接說明不可達蔫敲，且返回值為空列表：
[] - 如果兩個頂點不需要松弛就可以得到最短路徑，那么在 path 矩陣中對應(yīng)點的值就為初始值 -1炭玫，這代表了這兩個頂點鄰接奈嘿，在
getShortestPath函數(shù)中是需要判斷的 - 如果兩個頂點需要松弛才能得到最短路徑，那么在 path 矩陣中對應(yīng)點的值就不為 -1吞加，那么需要遞歸調(diào)用
back_path函數(shù)
- 如果兩個頂點不可達或者這兩個頂點為同一個頂點哎甲，那么直接說明不可達蔫敲，且返回值為空列表：
-
back_path函數(shù)- 之前說了裙犹，path 矩陣中記錄的是每次松弛操作時的中間點，所以在函數(shù)中前后兩次調(diào)用本身
-
舉例說明
- 以測試2的截圖為例衔憨，嘗試頂點0到頂點3的最短路徑：
- 進入
getShortestPath(graph,path,i,j)叶圃，調(diào)用back_path(path,0,3,[0]) - 首先調(diào)用
back_path(path,0,3,[0])，發(fā)現(xiàn) path[0][3]=5践图，說明需要頂點5的中轉(zhuǎn) - 于是調(diào)用
back_path(path,0,5,[0])掺冠，發(fā)現(xiàn) path[0][5]=2，說明需要頂點2的中轉(zhuǎn) - 繼續(xù)調(diào)用
back_path(path,0,2,[0])平项，發(fā)現(xiàn)到頭了赫舒，頂點0和頂點2直接鄰接，于是不再遞歸下去了闽瓢，添加頂點2到最短路徑 shortestPath接癌，此時 [0,2] - 返回上層，調(diào)用
back_path(path,2,5,[0,2])扣讼，發(fā)現(xiàn)到頭了缺猛，頂點2和頂點5直接鄰接，于是不再遞歸下去了荔燎，添加頂點5到最短路徑 shortestPath，此時 [0,2,5] - 返回上層销钝，調(diào)用
back_path(path,5,3,[0,2,5])有咨，發(fā)現(xiàn)需要頂點4的中轉(zhuǎn) - 于是調(diào)用
back_path(path,5,4,[0,2,5])，發(fā)現(xiàn)到頭了蒸健，不再遞歸座享，添加頂點4到最短距離婉商，此時 [0,2,5,4] - 返回上層，調(diào)用
back_path(path,4,3,[0,2,5,4])渣叛，發(fā)現(xiàn)到頭了丈秩，不再遞歸，添加頂點3到最短距離淳衙，此時 [0,2,5,4,3] 已經(jīng)是最短距離了 - 注意：因為只要調(diào)用
back_path就會添加頂點進入最短路徑 shortestPath蘑秽，為了避免重復(fù)，加入了 if 判斷箫攀，直接過濾掉重復(fù)的頂點肠牲，因為最短路徑不可能繞圈子。
- 進入
- 以測試2的截圖為例衔憨，嘗試頂點0到頂點3的最短路徑：
源碼地址：https://github.com/edisonleolhl/DataStructure-Algorithm/blob/master/Graph/ShortestPath/floyd.py
