是一個基于動態規劃的全源最短路算法。它可以高效地求出圖上任意兩點之間的最短路
時間復雜度 O(n^3)
狀態轉移方程
f[i][j]=min(f[i][j],f[i][k]+f[k][j])
核心代碼?
void floyd(){for(int k=1;k<=n;k++)for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)s[i][j]=min(s[i][j],s[i][k]+s[k][j]);
}k就是一個中間值，每次把從i到j的距離與從i到k再從k到j的距離進行比較，選取最小值，做答案
?例如k等于1的時候可以更新4，2這個點k等于2的時候可以更新3，1這個點。。。。。。
例題B3647 【模板】Floyd 算法
給出一張由?n?個點?m?條邊組成的無向圖。
求出所有點對?(i,j)?之間的最短路徑。
輸入格式
第一行為兩個整數?n,m，分別代表點的個數和邊的條數。
接下來?m?行，每行三個整數?u,v,w，代表?u,v?之間存在一條邊權為?w?的邊。
輸出格式
輸出?n?行每行?n?個整數。
第?i?行的第?j?個整數代表從?i?到?j?的最短路徑。
輸入輸出樣例
輸入?
4 4 1 2 1 2 3 1 3 4 1 4 1 1
輸出?
0 1 2 1 1 0 1 2 2 1 0 1 1 2 1 0
說明/提示
對于?100%?的數據n≤100,m≤4500，任意一條邊的權值?w?是正整數且?1?w?1000。
#include<iostream>
using namespace std;
const int N=1e4,INF=1e9;
int s[N][N]; //用于存圖
int n,m,q;void floyd(){for(int k=1;k<=n;k++)for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)s[i][j]=min(s[i][j],s[i][k]+s[k][j]);
}int main(){cin>>n>>m;//初始化for(int i=1;i<=n;i++)for(int j=1;j<=n;j++) if(i==j)s[i][j]==0;else s[i][j]=INF; //s[i][j]代表從i到j的最短距離//把給的邊存入while(m--){int a,b,c;cin>>a>>b>>c;s[a][b]=min(s[a][b],c);s[b][a]=min(s[b][a],c); //可能給重復的值，取最小的那一個存入 } floyd();for(int i=1;i<=n;i++){for(int j=1;j<=n;j++)cout<<s[i][j]<<" ";cout<<endl;}return 0;
} ?
)