2019獨角獸企業重金招聘Python工程師標準>>>

我們之前分別討論了Dijkstra算法和Bellman-Ford算法，它們解決的都是單源最短路徑問題。本文討論的Floyd-Warshall算法（下稱FW算法）則適用于解決可有負權邊但不可有負權環的“全局最短路徑問題”（all-pairs shortest path problem，或叫做“任意兩點間的最短路徑問題”)。

為了方便闡述思路，下文的討論里默認處理的問題還滿足下面的特點：

有權圖

兩節點之間最多有一條邊

無自回路（任何節點無指向自身的邊）

下圖為一個示例：

不滿足上面三條限制的圖需要先進行轉化，然后才能用下述的FW算法來解決。其可行性和具體過程，留給讀者自行探索。

算法思路

若圖G有n個節點（即n = |V|），將這所有節點做任意一個排序，依次記為v_1, v_2, ..., v_n。對于任意的起點u和任意的終點w，從它們之間的路徑中挑出所有中間點只含前k個節點（即{v_1, v_2, ..., v_k}，其中k < n）的那些，組成一個集合記為P(u, w, k)，并且假設我們已經知曉其中最短路徑的長度，記為d(u, w, k)；那么從u到w的、所有中間點只含前k+1個節點的路徑組成的集合可以記為P(u, w, k+1)，它們中間最短者的長度可以記為d(u, w, k+1)。可以很容易想明白這么一個關系，P(u, w, k+1)是P(u, w, k)的一個超集，而且屬于前者而不屬于后者的路徑一定經過第k+1個節點，也就是v_(k+1)。如果P(u, w, k+1)中的某條最短路徑不經過v_(k+1)，那么d(u, w, k+1)就等于d(u, w, k)。如果經過，那么首先可以知道，這條最短路徑一定只經過v_(k+1)一次，否則路徑中有回路，與最短矛盾；這也意味著，這條路徑可以分為兩半——從u到v_(k+1)的路徑和從v_(k+1)到w的路徑，且有：

它們的中間點都只由前k個節點組成

前一半在所有從u到v_(k+1)的中間點只含前k個節點的路徑中一定是最短的，其長度為d(u, v_(k+1), k)

后一半在所有從v_(k+1)到w的中間點只含前k個節點的路徑中一定最短，其長度為d(v_(k+1), w, k)

那么此時這條最短路徑的長度為d(u, v_(k+1), k) + d(v_(k+1), w, k)。如下圖所示：

綜上，可以得到下面這條重要結論：

d(u, w, k+1) = min(d(u, w, k), d(u, v_(k+1), k) + d(v_(k+1), w, k))

要證明上面思路的正確性，我們還得考慮一下基礎情況。當k = 0時，對于圖中任意的起終點u和w，如果存在從u到w的邊，那么記d(u, w, 0) = G[u][w]，否則記d(u, w, 0) = ∞。如此一來，算法的循環不變性質可以表述為：

• 初始為真：在循環之前（k = 0）時，對于任意的u和w，d(u, w, k)確實為從u直接到w的最短路徑的長度（不存在時為無窮大）
• 迭代不變：這在前面已經證明
• 終止得證：那么在算法終止時，也就是第n次迭代結束后，d(u, w, n)的值為從u到w（中間點可以為所有節點）的最短路徑的長度

代碼實現

根據上面的思路，我們可以給出如下的代碼實現。下面的代碼出自Python Algorithms一書，稍有改動，下同。

from copy import deepcopy from math import infdef floyd_warshall(G):D = deepcopy(G)for v in G:for u in G:for w in G:current = D[u].get(w, inf)shortcut = D[u].get(v, inf) + D[v].get(w, inf)D[u][w] = min(current, shortcut)return D

在上面的代碼里，圖G由G表示，它是一個dict的dict：對于G中任意節點v，G[v]本身也是一個dict，如果存在邊(v, w)，則G[v][w]是該邊的權重。因為這里限制了自回路的情況，對任意的節點v，v不在G[v]當中，故而有G[v].get(v, inf)等于inf而非0；這一點請留意。

首先講講算法的空間復雜度。在上節的思路分析里，我們用了起點、終點、可用中間點的最大序號三個參數來表示子問題的解，所以很容易以為代碼中需要一張三維的表來做記錄，而實際上這里相當于只用了一張二維的表，D，它的結構與G完全相同。其實說到這里，應該已經可以明確，Floyd-Warshall算法運用的是動態規劃思想。動態規劃的關鍵在于把原問題拆分為互有重疊的子問題。FW算法就是按照可用中間點的最大序號，把原問題分拆成了很多級子問題。而D就是用來存儲子問題的解的。之所以不需要三維而只需二維的表，是這個大問題的內在結構決定的：每一級的子問題只依賴于低一級的子問題的解，而不需要更低級別的子問題的解，所以可以覆蓋原來的值，故而總體上的空間復雜度為O(|V|**2)。

算法的時間復雜度顯然為O(|V|**3)，因為有三層循環。要注意的是循環的順序：最外層的循環變量一定得是中間點。這是因為子問題是以可用中間點的最大序號來分級的，在解決某一級子問題的時候，需要所有低一級的子問題都已經有解了。如果

另外，上面的代碼僅僅算出每一對節點(u, w)間最短路徑的距離，并沒有給出一條(u, w)間的最短路徑。如果需要，可以將代碼做如下修改，使其不僅僅給出距離，也記錄最短路徑本身（所有最短路徑中的一條）：

from copy import deepcopy from math import infdef floyd_warshall(G):D, V = deepcopy(G), {}for u in G:for w in G:if G[u].get(w, inf) == inf:V[u, w] = Noneelse:V[u, w] = ufor v in G:for u in G:for w in G:current = D[u].get(w, inf)shortcut = D[u].get(v, inf) + D[v].get(w, inf)if shortcut < current:V[u][w] = shortcutV[u, w] = V[v, w]return D, V

在算法結束時，P[u, w]所記錄的可能是如下三種情況：

None，說明沒有路徑從u到w

u，說明從u到w的邊即是最短路徑

u和w之外的某個節點，說明從u到w有條最短路徑經過該節點（且該節點在所有中間點中序號最大）

這時候就可以用下面的方法來獲取兩點間的某一條最短路徑（不包含兩個端點）：

def shortest_path(V, u, w):assert (u, w) in Vif V[u, w] == None:return None #不存在從u到w的路徑if V[u, w] == u:return [] #從u到w的某條最短路徑沒有其他中間點v = V[u, w]return shortest_path(V, u, v) + [v] + shortest_path(V, v, w)

強調一點

從上面的分析來看，FW算法的思想說穿了不難理解，相應地，其代碼實現也可以很簡單。但其精妙或者說最難想到之處，就是它構建子問題的方法：在縮小了問題規模的同時保證了子問題與原問題有同樣的結構。做到這一點，依靠的是引入一個不怎么直觀的限制：路徑中間點所能選擇的集合。

其實這種引入新的限制參數來分拆問題的技巧，尤其在動態規劃的算法里，不算少見。例如硬幣面額組合問題的解法，就用到了這個技巧。以后在遇到新問題時，如果覺得可以用動態規劃來解，但是不知道如何分拆為子問題時，不妨打開下思路，試試看能不能引入新的限制，也許就能豁然開朗。

結語

本文討論了Floyd-Warshall算法，這里對關鍵點做個總結：

• FW算法解決的是全局最短距離問題，適用的圖中允許有負權邊，但不可有負權環
• FW算法運用了動態規劃的思想，其核心在于限制路徑中間點的選擇，將原問題按照中間點最大序號分拆為層層依賴的子問題
• FW算法的時間負責度為O(|V|**3)，空間復雜度可以達到O(|V|**2)

轉載于:https://my.oschina.net/qiaotoubao/blog/738646

總結

以上是生活随笔為你收集整理的理解Floyd-Warshall算法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。