Floyd-Warshall算法及例题
Floyd算法
概要
Floyd可以⼀次性求出所有节点之间的最短距离
这种算法主要采⽤了动态规划的思想，假设求从i到j的最短路径，那么寻⼀个中间位置k，如果从i到k距离加上k到j的距离⽐直接从i到j ⼩，那么就更新从i到j的最短路径
根据上⾯的设想，Floyd是由三层for循环组成的，第⼀层for循环显然是k，因为我们不知道谁来借助k，所以k应该放在最外⾯；⾥⾯的两层分别是i和j，这不难理解。
朴素的Floyd如下
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(edge[i][j]> edge[i][k]+ edge[k][j]) edge[i][j]= edge[i][k]+ edge[k][j];
}
}
}
}
3
可以看出Floyd算法时间复杂度是O（n），只能解决⼀些⼩图的最短路问题，但是代码书写简单，且能⼀次性求出所有边的最短路练习
hdu2544
这道题可⽤floyd，不加任何优化，旨在熟悉算法框架
#include<string>
#include<cmath>
#include<iomanip>
#include<queue>
#include<stack>
using namespace std;
typedef long long ll;
const int MAXN =500;
int INF =0x3f3f3f3f;
int edge[MAXN][MAXN];
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(edge[i][j]> edge[i][k]+ edge[k][j]) edge[i][j]= edge[i][k]+ edge[k][j];
}
}
}
}
int main(){
int n,m,a,b,c;
while(cin>>n>>m){
if(n ==0&&m ==0)break;
memset(edge,0x3f,sizeof edge);
for(int i=0;i<m;i++){
cin>>a>>b>>c;
edge[a][b]=min(edge[a][b],c);
edge[b][a]= edge[a][b];
}
Floyd(n);
cout<<edge[1][n]<<endl;
}
return0;
}
hdu3631
题⽬要求借助标记过的点寻最短路，显然是floyd算法思想，⼜n范围不⼤，考虑使⽤floyd 需要注意⾃⼰到⾃⼰的距离问题，需要设置为0，输出格式注意⼀下
#include<string>
#include<cmath>
#include<iomanip>
#include<queue>
#include<stack>
using namespace std;
typedef long long ll;
const int MAXN =2e5+100;
int edge[500][500];
int vis[MAXN];
const int INF =0x3f3f3f3f;
void floyd(int k,int n){
for(int i=0;i<n;i++){
if(edge[i][k]!=INF)
for(int j=0;j<n;j++){
if(edge[i][j]> edge[i][k]+ edge[k][j]){
edge[i][j]= edge[i][k]+ edge[k][j];
}
}
}
}
int main(){
int n,m,q,a,b,c,op;
int times =1;
while(~scanf("%d%d%d",&n,&m,&q)){
if(n ==0&&m ==0&&q ==0)break;
if(times !=1)printf("\n");
memset(edge,0x3f,sizeof edge);include和contain
memset(vis,0,sizeof vis);
for(int i=0;i<n;i++) edge[i][i]=0;
for(int i=0;i<m;i++){
scanf("%d%d%d",&a,&b,&c);
if(edge[a][b]> c) edge[a][b]= c;
}
printf("Case %d:\n",times++);
while(q--){
scanf("%d",&op);
if(op ==0){
scanf("%d",&a);
if(vis[a]){
printf("ERROR! At point %d\n",a);
}
else{
vis[a]=1;
floyd(a,n);
}
}else{
scanf("%d%d",&a,&b);
if(!vis[a]||!vis[b])printf("ERROR! At path %d to %d\n", a, b);
else if(edge[a][b]== INF)printf("No such path\n");
else printf("%d\n",edge[a][b]);
}
}
}
return0;
}
hdu1704
题⽬意思是给出了若⼲⽐赛关系，问不能确定的冠军数量
抽象成⼀个图，那么很明显如果两个点之间可达，不论顺序，那么他们之间就能确定谁是冠军此题是使⽤floyd算法求图的传递闭包，有关传递闭包概念如下
所以直接使⽤floyd算法，如果从i到j和j到i都没有路径，则构成⼀个答案
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<iomanip>
#include<queue>
#include<stack>
using namespace std;
typedef long long ll;
const int MAXN =2e5+100;
int edge[600][600];
const int INF =0x3f3f3f3f;
void floyd(int n){
for(int k=1;k<=n;k++){
for(int i=1;i<=n;i++){
if(edge[i][k]!= INF)
for(int j=1;j<=n;j++){
if(edge[i][j]> edge[i][k]+ edge[k][j]){
edge[i][j]= edge[i][k]+ edge[k][j];
}
}
}
}
}
int main(){
int t,n,m,x,y;
cin>>t;
while(t--){
memset(edge,0x3f,sizeof edge);
cin>>n>>m;
for(int i=0;i<m;i++){
cin>>x>>y;
edge[x][y]=1;
}
floyd(n);
int ans =0;
for(int i=1;i<=n;i++){
for(int j=i+1;j<=n;j++){
if(edge[i][j]== INF&&edge[j][i]== INF){
ans++;
}
}
}
cout<<ans<<endl;
}
return0;
}
洛⾕P1119
看数据范围应该是floyd。道路不需要修，⽽村庄需要修，每修⼀个村庄相当于图中加⼀个点，如果每加⼀个点就跑⼀次floyd那么显然不合理，题⽬给出村庄修复时间是升序，这是很⽅便的，可以考虑每次加的点作为floyd中的中介点k，按照规定时间范围遍历，如果x 和y能够借助k互相达到，那么更新最短路，这个时候不需要考虑x或者y是否修好，因为如果没修好就输出-1，但是最短路需要更新