楔子

long long ago就已經知道了Floyd算法，關鍵代碼就4行，也容易記住，上上周又看到了Floyd，都說是動態規劃，所以特意去學了一圈動態規劃，今天終于又回到了它

狀態方程：

d[k][i][j]定義：“只能使用第1號到第k號點作為中間媒介時，點i到點j之間的最短路徑長度。”
在動態規劃算法中，處于首要位置、且也是核心理念之一的就是狀態的定義
這個大家喜歡把它叫做“松弛操作”，也就是relax
對于d[k][i][j]（即使用1號到k號點中的所有點作為中間媒介時，i和j之間的最短路徑），可以分為兩種情況:

1）i到j的最短路不經過k；（ 2）i到j的最短路經過了k。不經過點k的最短路情況下，d[k][i][j]=d[k-1][i][j]。經過點k的最短路情況下，d[k][i][j]=d[k-1][i][k]+d[k-1][k][j]。

因此，綜合上述兩種情況，便可以得到Floyd算法的動態轉移方程：
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[0][i][j]=w(i, j)，d[k][0][j]=0,d[k][i][0]=0

原始的實現如下：

# 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]） import numpy as np def floyd_original(graph):vertex_num = len(graph)list = np.full((vertex_num+1,vertex_num+1,vertex_num+1),np.inf)list[:,0,:] = 0list[:,:,0] = 0for i in range(1,vertex_num+1):for j in range(1,vertex_num+1):list[0,i,j] = graph[i-1,j-1]for k in range(1,vertex_num+1):for i in range(1,vertex_num+1):for j in range(1,vertex_num+1):list[k,i,j] = min(list[k-1,i,j],list[k-1,i,k]+list[k-1,k,j])return list[vertex_num,1:,1:]

觀察DP數組，可以做空間優化，類似于背包問題使用滾動數組優化：

1、d[k][i][j]只與d[k-1][i][j], d[k-1][i][k]+d[k-1][k][j]有關，也就是只和d[k-1]，那么我們就可以只用一個二維數組代替三維的數組；

2、然后看我們是否需要注意遍歷這個二維數組的順序（例如01背包問題需要逆序遍歷才能保證用的數據是上一層的，完全背包需要順序遍歷才能保證用的數據是更新后的這一層的），假如采取順序的話，d[k-1][i][j]這個沒問題，d[k-1][i][k]+d[k-1][k][j]這個k永遠是小于或者等于i的，所以d[k-1][i][k]+d[k-1][k][j]取的是應該是更新后的數據，他們在已更新的區域里，那不是不能使用滾動數組了？但是事實已經證明可以這么用，后來發現一個解釋：

3、有這樣一條重要的性質，dp[k-1][i][k]和dp[k-1][k][j]是不會在第k階段改變大小的。也就是說，凡是和k節點相連的邊，在第k階段的值都不會變。如何簡單證明呢？我們可以把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]

也就是說在第k-1階段和第k階段，點i和點k之間的最短路徑長度是不變的。相同可以證明，在這兩個階段中，點k和點j之間的的最短路徑長度也是不變的。因此，對于使用滾動數組的轉移方程d[i][j] = min(d[i][j], d[i][k]+d[k][j])來說，賦值號右側的d[i][j], d[i][k]和d[k][j]的值都是上一階段（k-1階段）的值，可以放心地被用來計算第k階段時d[i][j]的值。
有沒有很坑? 繞了一圈又回到不熟悉的東西上去了
仔細看一遍上述的公式就懂了。
所以我們可以使用滾動數組來優化空間。

實現如下：

import numpy as np def floyd(graph):vertex_num = len(graph) list = np.zeros((vertex_num+1,vertex_num+1))for i in range(1,vertex_num+1):for j in range(1,vertex_num+1):list[i,j] = graph[i-1,j-1]for k in range(1,vertex_num+1):for i in range(1,vertex_num+1):for j in range(1,vertex_num+1):list[i,j] = min(list[i,j],list[i,k]+list[k,j])return list[1:,1:]

運行結果

#%% graph = np.full((7,7),np.inf) graph[0,:3] = [0,1,2] graph[1,:4] = [1,0,3,4] graph[2,:4] = [2,3,0,6] graph[3,1:5] = [4,6,0,7] graph[4,3:6] = [7,0,9] graph[5,4:7] = [9,0,10] graph[6,5:7] = [10,0]print floyd_original(graph)print floyd(graph)[[ 0. 1. 2. 5. 12. 21. 31.][ 1. 0. 3. 4. 11. 20. 30.][ 2. 3. 0. 6. 13. 22. 32.][ 5. 4. 6. 0. 7. 16. 26.][12. 11. 13. 7. 0. 9. 19.][21. 20. 22. 16. 9. 0. 10.][31. 30. 32. 26. 19. 10. 0.]][[ 0. 1. 2. 5. 12. 21. 31.][ 1. 0. 3. 4. 11. 20. 30.][ 2. 3. 0. 6. 13. 22. 32.][ 5. 4. 6. 0. 7. 16. 26.][12. 11. 13. 7. 0. 9. 19.][21. 20. 22. 16. 9. 0. 10.][31. 30. 32. 26. 19. 10. 0.]]

總結

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

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