弗洛伊德算法大致有點像dp的推導
dp[i][j] = min(dp[i][k] + dp[k][j], dp[i][j]),
其中 i 是起始點，j 是終止點。k是它們經過的中途點。
通過這個公式不斷地更新dp[i][j],得到最短路徑長。
我們先定義兩個矩陣，minpath[i][j],表示的是從 i 到 j 當前得到的最短路，
road[i][j] = k.表示的是從 i 到 j 點要經過的點是 k 然后不斷更新road[k][j],
直到k == j。
這個可以適用與有向圖和無向圖，就看你minpath[i][j] 怎么初始化了，

#include<iostream> using namespace std; const int inf = 0x3f3f3ff3; const int maxn = 110; int minpath[maxn][maxn],road[maxn][maxn], n, m, s, t; void init() {for(int i = 1; i <= n; i++)for(int j = 1; j <= n; j++)if(i ==j) minpath[i][j] = 0, road[i][j] = j;else minpath[i][j] = inf, road[i][j] = j; } void Floyed() {for(int k = 1; k <= n; k++) {//中間轉折點。for(int i = 1; i <= n; i++) {//起始點。for(int j = 1; j <= n; j++) {//終點。if(minpath[i][j] > minpath[i][k] + minpath[k][j]) {//當前的路是否更好，minpath[i][j] = minpath[i][k] + minpath[k][j];road[i][j] = road[i][k];}}}}for(int i = 1; i <= n; i++) {t = s;cout << minpath[s][i] <<endl;//s->t的花費。while(t != i) {//從起點開始輸出路徑。cout << t << "->";t = road[t][i];//不斷更新路徑點。}cout << i <<endl;} } int main() {cin >> n >> m >> s;//輸入表示n個點，m條邊，求s為起始點，求其到 n 個點的距離。init();//初始化，int x, y;for(int i = 0; i < m; i++) {//輸入邊。cin >> x >> y;cin >> minpath[x][y];}Floyed();//算法本體，return 0; }

---

最后運行情況，加上了路徑的輸出。

說明一下我上面的代碼并不是這道題目的正解，就算上面的代碼除去我的路徑輸出也是錯的，
題目的n到了1e4，而這種方法最多就是處理一兩百的數據，
這里就是為了方便舉個例子。

總結

以上是生活随笔為你收集整理的最短路弗洛伊德(Floyd)算法加保存路径的全部內容，希望文章能夠幫你解決所遇到的問題。

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