Floyd–Warshall（簡(jiǎn)稱Floyd算法）是一種著名的解決任意兩點(diǎn)間的最短路徑（All Paris Shortest Paths，APSP）的算法。從表面上粗看，Floyd算法是一個(gè)非常簡(jiǎn)單的三重循環(huán)，而且純粹的Floyd算法的循環(huán)體內(nèi)的語(yǔ)句也十分簡(jiǎn)潔。我認(rèn)為，正是由于“Floyd算法是一種動(dòng)態(tài)規(guī)劃（Dynamic Programming）算法”的本質(zhì)，才導(dǎo)致了Floyd算法如此精妙。

因此，這里我將從Floyd算法的狀態(tài)定義、動(dòng)態(tài)轉(zhuǎn)移方程以及滾動(dòng)數(shù)組等重要方面，來(lái)簡(jiǎn)單剖析一下圖論中這一重要的基于動(dòng)態(tài)規(guī)劃的算法——Floyd算法。

在動(dòng)態(tài)規(guī)劃算法中，處于首要位置、且也是核心理念之一的就是狀態(tài)的定義。在這里，把d[k][i][j]定義成：

“只能使用第1號(hào)到第k號(hào)點(diǎn)作為中間媒介時(shí)，點(diǎn)i到點(diǎn)j之間的最短路徑長(zhǎng)度。”

圖中共有n個(gè)點(diǎn)，標(biāo)號(hào)從1開(kāi)始到n。因此，在這里，k可以認(rèn)為是動(dòng)態(tài)規(guī)劃算法在進(jìn)行時(shí)的一種層次，或者稱為“松弛操作”。

• d[1][i][j]表示只使用1號(hào)點(diǎn)作為中間媒介時(shí)，點(diǎn)i到點(diǎn)j之間的最短路徑長(zhǎng)度；
• d[2][i][j]表示使用1號(hào)點(diǎn)到2號(hào)點(diǎn)中的所有點(diǎn)作為中間媒介時(shí)，點(diǎn)i到點(diǎn)j之間的最短路徑長(zhǎng)度；
• d[n-1][i][j]表示使用1號(hào)點(diǎn)到(n-1)號(hào)點(diǎn)中的所有點(diǎn)作為中間媒介時(shí)，點(diǎn)i到點(diǎn)j之間的最短路徑長(zhǎng)度d[n][i][j]表示使用1號(hào)到n號(hào)點(diǎn)時(shí)，點(diǎn)i到點(diǎn)j之間的最短路徑長(zhǎng)度。

有了狀態(tài)的定義之后，就可以根據(jù)動(dòng)態(tài)規(guī)劃思想來(lái)構(gòu)建動(dòng)態(tài)轉(zhuǎn)移方程。

?????? 動(dòng)態(tài)轉(zhuǎn)移的基本思想可以認(rèn)為是建立起某一狀態(tài)和之前狀態(tài)的一種轉(zhuǎn)移表示。按照前面的定義，d[k][i][j]是一種使用1號(hào)到k號(hào)點(diǎn)的狀態(tài)，可以想辦法把這個(gè)狀態(tài)通過(guò)動(dòng)態(tài)轉(zhuǎn)移，規(guī)約到使用1號(hào)到(k-1)號(hào)的狀態(tài)，即d[k-1][i][j]。對(duì)于d[k][i][j]（即使用1號(hào)到k號(hào)點(diǎn)中的所有點(diǎn)作為中間媒介時(shí)，i和j之間的最短路徑），可以分為兩種情況：

i到j(luò)的最短路不經(jīng)過(guò)k；

i到j(luò)的最短路經(jīng)過(guò)了k；

具體來(lái)說(shuō)：

不經(jīng)過(guò)點(diǎn)k的最短路情況下，d[k][i][j]=d[k-1][i][j]。

經(jīng)過(guò)點(diǎn)k的最短路情況下，d[k][i][j]=d[k-1][i][k]+d[k-1][k][j]。

因此，綜合上述兩種情況，便可以得到Floyd算法的動(dòng)態(tài)轉(zhuǎn)移方程：

d[k][i][j] = min(d[k-1][i][j], d[k-1][i][k]+d[k-1][k][j])（k,i,j∈[1,n]）

最后，d[n][i][j]就是所要求的圖中所有的兩點(diǎn)之間的最短路徑的長(zhǎng)度。在這里，需要注意上述動(dòng)態(tài)轉(zhuǎn)移方程的初始（邊界）條件，即d[0][i][j]=w(i, j)，也就是說(shuō)在不使用任何點(diǎn)的情況下（“松弛操作”的最初），兩點(diǎn)之間最短路徑的長(zhǎng)度就是兩點(diǎn)之間邊的權(quán)值（若兩點(diǎn)之間沒(méi)有邊，則權(quán)值為INF；且我比較偏向在Floyd算法中把圖用鄰接矩陣的數(shù)據(jù)結(jié)構(gòu)來(lái)表示，因?yàn)楸阌诓僮?#xff09;。當(dāng)然，還有d[i][i]=0（i∈[1,n]）。

這樣我們就可以編寫(xiě)出最為初步的Floyd算法代碼：

void floyd_original() {for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)d[0][i][j]=graph[i][j];for(int k=1;k<=n;k++)for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)d[k][i][j]=min(d[k-1][i][j],d[k-1][i][k]+d[k-1][k][j]); }

幾乎所有介紹動(dòng)態(tài)規(guī)劃中最為著名的“0/1背包”問(wèn)題的算法書(shū)籍中，都會(huì)進(jìn)一步介紹利用滾動(dòng)數(shù)組的技巧來(lái)進(jìn)一步減少算法的空間復(fù)雜度，使得0/1背包只需要使用一維數(shù)組就可以求得最優(yōu)解。而在各種資料中，最為常見(jiàn)的Floyd算法也都是用了二維數(shù)組來(lái)表示狀態(tài)。那么，在Floyd算法中，是如何運(yùn)用滾動(dòng)數(shù)組的呢？

再次觀察動(dòng)態(tài)轉(zhuǎn)移方程?d[k][i][j] = min(d[k-1][i][j], d[k-1][i][k]+d[k-1][k][j])，可以發(fā)現(xiàn)每一個(gè)第k階段的狀態(tài)（d[k][i][j]），所依賴的都是前一階段（即第k-1階段）的狀態(tài)（如d[k-1][i][j]，d[k-1][i][k]和d[k-1][k][j]）。

上圖描述了在前面最初的Floyd算法中，計(jì)算狀態(tài)d[k][i][j]時(shí)，d[k-1][ ][ ]和d[k][ ][ ]這兩個(gè)二維數(shù)組的情況

d[k-1][][]表示第k-1階段時(shí)，圖中兩點(diǎn)之間最短路徑長(zhǎng)度的二維矩陣；

d[k][][]表示第k階段時(shí)，圖中兩點(diǎn)之間最短路徑長(zhǎng)度的二維矩陣；

紅色帶有箭頭的有向線段指示了規(guī)劃方向。灰色表示已經(jīng)算過(guò)的數(shù)組元素。白色代表還未算過(guò)的元素。由于d[k-1][][]和d[k][][]是兩個(gè)相互獨(dú)立的二維數(shù)組，因此利用d[k-1][i][j]，d[k-1][i][k]和d[k-1][k][j]（皆處于上方的二維數(shù)組中）來(lái)計(jì)算d[k][i][j]時(shí)沒(méi)有任何問(wèn)題。

那如何利用一個(gè)二維數(shù)組來(lái)實(shí)現(xiàn)滾動(dòng)數(shù)組，以減小空間復(fù)雜度呢？

上圖是使用滾動(dòng)數(shù)組，在第k階段，計(jì)算d[i][j]時(shí)的情況。此時(shí)，由于使用d[][]這個(gè)二維數(shù)組作為滾動(dòng)數(shù)組，在各個(gè)階段的計(jì)算中被重復(fù)使用，因此數(shù)組中表示階段的那一維也被取消了。

在這圖中，白色的格子，代表最新被計(jì)算過(guò)的元素（即第k階段的新值），而灰色的格子中的元素值，其實(shí)保存的還是上一階段（即第k-1階段）的舊值。因此，在新的d[i][j]還未被計(jì)算出來(lái)時(shí)，d[i][j]中保存的值其實(shí)就對(duì)應(yīng)之前沒(méi)有用滾動(dòng)數(shù)組時(shí)d[k-1][i][j]的值。此時(shí)，動(dòng)態(tài)轉(zhuǎn)移方程在隱藏掉階段索引后就變?yōu)?#xff1a;

d[i][j] = min(d[i][j], d[i][k]+d[k][j])（k,i,j∈[1,n]）

賦值號(hào)左側(cè)d[i][j]就是我們要計(jì)算的第k階段是i和j之間的最短路徑長(zhǎng)度。在這里，需要確保賦值號(hào)右側(cè)的d[i][j], d[i][k]和d[k][j]的值是上一階段（k-1階段）的值。前面已經(jīng)分析過(guò)了，在新的d[i][j]算出之前，d[i][j]元素保留的值的確就是上一階段的舊值。

但至于d[i][k]和d[k][j]呢？我們無(wú)法確定這兩個(gè)元素是落在白色區(qū)域（新值）,還是灰色區(qū)域（舊值）。

好在有這樣一條重要的性質(zhì)：dp[k-1][i][k] 和 dp[k-1][k][j] 是不會(huì)在第k階段改變大小的。也就是說(shuō)，凡是和k節(jié)點(diǎn)相連的邊，在第k階段的值都不會(huì)變。如何簡(jiǎn)單證明呢？

我們可以把j=k代入之前的d[k][i][j]=min(d[k-1][i][j], d[k-1][i][k]+d[k-1][k][j])方程中，即：

d[k][i][k]

= min(d[k-1][i][k], d[k-1][i][k]+d[k-1][k][k])

= min(d[k-1][i][k], d[k-1][i][k]+0)

= d[k-1][i][k]

也就是說(shuō)在第k-1階段和第k階段，點(diǎn)i和點(diǎn)k之間的最短路徑長(zhǎng)度是不變的。相同可以證明，在這兩個(gè)階段中，點(diǎn)k和點(diǎn)j之間的的最短路徑長(zhǎng)度也是不變的。

因此，對(duì)于使用滾動(dòng)數(shù)組的轉(zhuǎn)移方程d[i][j] = min(d[i][j], d[i][k]+d[k][j])來(lái)說(shuō)，賦值號(hào)右側(cè)的d[i][j], d[i][k]和d[k][j]的值都是上一階段（k-1階段）的值，可以放心地被用來(lái)計(jì)算第k階段時(shí)d[i][j]的值。

利用滾動(dòng)數(shù)組改寫(xiě)后的Floyd算法代碼如下：

void floyd() {for(int k = 1; k <= n; k++)for(int i = 1; i <= n; i++)for(int j = 1; j <= n; j++)d[i][j] = min(d[i][j], d[i][k] + d[k][j]); }

?

總結(jié)

以上是生活随笔為你收集整理的Floyd算法的动态规划本质的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。