【概述】?

Floyd 算法又稱為插點法，是一種用于尋找給定的加權圖中多源點之間最短路徑的算法。

其最大特點是可以計算出現負邊權時的最短路，實際應用中，很多題目不是問如何用 Floyd 求最短路，而是用 Floyd 的動態規劃思想來解決類似 Floyd 的問題。

其時間復雜度是?O(N*N*N)，N是頂點數。

【極大值的選擇】

設置無窮大時，0x7fffffff 是 32-bit int 的最大值，如果這個無窮大只用于一般的比較，那么?0x7fffffff 是一個完美的選擇，但在更多情況下，其并不是一個好的選擇。

在最短路的松弛操作時，如果 u、v 間無邊，那么 w[u][v]=INF，此時若 INF 取?0x7fffffff，那么 dis[u]+w[u][v] 會溢出而變成負數，此時松弛操作便會出錯，準確來說，0x7fffffff 不能滿足無窮大加一個有窮的數依然是無窮大，而是變成了一個很小的負數。

if(dis[u]+w[u][v]<dis[v]) dis[v]=dis[u]+w[u][v];

由于要找一個能夠滿足無窮大加無窮大依然是無窮大的數，因此，可以選用 0x3f3f3f3f

0x3f3f3f3f 的十進制是 1061109567，是 10^9 級別的，與 0x7fffffff 一個數量級，而一般場合下的數據都是小于10^9的，所以它可以作為無窮大使用而不致出現數據大于無窮大的情形。?

另一方面，由于一般的數據都不會大于 10^9，所以當我們把無窮大加上一個數據時，它并不會溢出，事實上 0x3f3f3f3f + 0x3f3f3f3f = 2122219134，這個數雖然非常大但卻沒有超過 32-bit int 的表示范圍，因此?0x3f3f3f3f 還滿足了無窮大加無窮大還是無窮大的需求。

此外，當想將某個數組清零或全部賦值為 -1，通常會使用 memset() 函數，但是當想將某個數組全部賦值為無窮大時，就不能使用memset 函數而是寫循環了，因為 memset 是按字節操作的，它能夠對數組清零是因為 0 的每個字節都是 0。但如果將無窮大設為 0x3f3f3f3f，由于其每個字節都是 0x3f，因此可以直接使用 memset() 函數來操作。

【算法核心】

1.初始化：

設 dis[i][j] 為 i、j 兩點的距離，w[i][j] 為 i、j 兩點的權值。

若點 u、v 有邊連接，則：dis[u][v]=w[u][v]，即：初始化兩點最短距離為兩點權值。

若點 u、v 無邊連接，則：dis[u][v]=0x3f3f3f3f，即：初始化為一極大值。

2.算法主體

for(int k=1;k<=n;k++)//第一重循環為i→j的中間點kfor(int i=1;i<=n;i++)//第二重循環為起點ifor(int j=1;j<=n;j++)//第三重循環為終點jif(dis[i][j]>dis[i][k]+dis[k][j])//如果i→k的距離加上k→j的距離小于i→j的距離dis[i][j]=dis[i][k]+dis[k][j];//更新最短路徑

3.算法結束：dis[i][j] 即為 i→j 的最短路徑。

【模版】

int G[N][N]; int path[N][N];//path[i][j]=x表示i到j的路徑上除i外的第一個點是x void init(int n) {for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {if (i == j)G[i][j] = 0;elseG[i][j] = INF;path[i][j] = j;}} } void floyd(int n) {for (int k = 1; k <= n; k++) { //枚舉中間點for (int i = 1; i <= n; i++) { //枚舉起點for (int j = 1; j <= n; j++) { //枚舉終點if (G[i][k] < INF && G[k][j] < INF) {if (G[i][j] > G[i][k] + G[k][j]) { //松弛操作G[i][j] = G[i][k] + G[k][j];path[i][j] = path[i][k]; //更新路徑} else if (G[i][j] == G[i][k] + G[k][j] && path[i][j] > path[i][k]) { //在最短路相同的情況下，更新字典序最小的路徑path[i][j] = path[i][k]; //最終path中存的是字典序最小的路徑}}}}} } int main() {int n, m;while (scanf("%d%d", &n, &m) != EOF) {init(n);for (int i = 1; i <= m; i++) {int x, y, dis;scanf("%d%d%d", &x, &y, &dis);//無向圖添邊一次,有向圖添邊兩次G[x][y] = dis;G[y][x] = dis;}floyd(n);for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++)printf("%d ", G[i][j]);printf("\n");}}return 0; }

?

總結

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

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