目錄

介紹：?

代碼：?

結(jié)果：?

介紹：?

弗洛伊德算法（Floyd algorithm）也稱為Floyd-Warshall算法，是一種用于求解所有節(jié)點(diǎn)對之間的最短路徑的動(dòng)態(tài)規(guī)劃算法。它使用了一個(gè)二維數(shù)組來存儲所有節(jié)點(diǎn)之間的最短距離，該數(shù)組的初始值為節(jié)點(diǎn)之間的直接距離或無窮大。然后，算法對數(shù)組進(jìn)行多次迭代，每次迭代都嘗試通過一個(gè)中間節(jié)點(diǎn)更新節(jié)點(diǎn)之間的距離值，直到所有節(jié)點(diǎn)之間的最短距離被計(jì)算出來。該算法的時(shí)間復(fù)雜度為O(n^3)，適用于有向圖或無向圖，但不能處理帶有負(fù)權(quán)邊的圖。

代碼：?

#include<iostream>//弗洛伊德算法
using namespace std;
int G[100][100],D[100][100],Path[100][100];
int n, t, maxlen=999;
void Floyd()
{for (int i = 0; i < n; i++)//初始化最短路徑和前驅(qū)for(int j=0; j<n; j++){D[i][j] = G[i][j];if (D[i][j] < maxlen && i != j)//i和j之間有弧，前驅(qū)設(shè)為iPath[i][j] = i;else//i和j之間無弧，前驅(qū)設(shè)為-1Path[i][j] = -1;}for(int k=0;k<n;k++)for(int i=0;i<n;i++)for (int j = 0; j < n; j++){if (D[i][k] + D[k][j] < D[i][j])//i到j(luò)經(jīng)過k點(diǎn)有更短路徑{D[i][j] = D[i][k] + D[k][j];//更新D[i][j]Path[i][j] = Path[k][j];//更改前驅(qū)}}for (int i = 1; i < n; i++)//訪問從0點(diǎn)到各點(diǎn)的最短距離{cout << "0點(diǎn)到" << i << "的最短路徑權(quán)值為：" << D[0][i] << " ";cout << "路徑為：";int a = Path[0][i];cout << i<< " ";while (a != 0){cout << a << " ";a = Path[0][a];}cout << endl;}
}
int main()
{cout << "輸入頂點(diǎn)數(shù)：" << endl;cin >> n;for (int i = 0; i < n; i++)for (int j = 0; j < n; j++)G[i][j] = maxlen;cout << "輸入邊數(shù)：" << endl;cin >> t;for (int i = 0; i < t; i++){int v1, v2, w;cin >> v1 >> v2 >> w;G[v1][v2] = w;}Floyd();
}

結(jié)果：?