我们作为刚学图论的小蒟蒻，先接触到的算法一定是图上最短路径算法。而最短路算法中最简单的当属Floyd-Warshall算法。下面是一些基本介绍：
该算法可以计算图上任意两点间的最短路径
时间复杂度：O(n^3)
适用情况：适用出现负边权的情况
算法伪代码：
弗洛伊德算法的基本思想是动态规划，我们枚举每一个点，并以其为中间节点更新任意两点间的最小距离，伪代码：
#define maxn 最大节点数
#define inf 0x7fffffff-2
long long val[maxn][maxn];
long long dis[maxn][maxn];
inline void floyd(){
for(int i=1;i<=maxn;i++)
for(int j=1;j<=maxn;j++)
if(val[i][j])
dis[i][j]=val[i][j];
else
dis[i][j]=inf;
for(int k=1;k<=maxn;k++)
for(int i=1;i<=maxn;i++)
for(int j=1;j<=maxn;j++)
if(dis[i][j]>dis[i][k]+dis[k][j])
dis[i][j]=dis[i][k]+dis[k][j];
}
此时，dis[i][j]就是从i节点到j节点的最短路径。
算法分析&&思路讲解
- 初始化：我们在初始化时，将有边相连的节点间distance更新为边权值，无边相连直接设为极大值。
- 动态规划：对于每个节点，我们都让它做一次中间节点（k），然后分别枚举另外两个节点（i，j），如果当前从i到j的最短路大于从i到k的最短路加上从j到k的最短路，即从i到j如果经过k点会路径更短，那么我们更新从i到j的最短路。
- 算法结束，我们得到了所有的最短路。
需要强调的一点是，floyd中k的循环必须写在最外层，否则会导致动态规划状态转移发生错误！
例题讲解：Luogu P2935
传送门
不难发现，题目是让我们求所有牧场到喜欢的牧场的最短路，这就是所谓的多源最短路问题。对于这道题思路如下：
- 用floyd求出所有最短路。
- 枚举每个点，求出最小平均距离。
该题数据较小，这种思路完全可以通过。
代码：
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3fffffff
int n,m,f,u,v,t;
int square[501][501];
long long dis[501][501];
int like[501];
int main(){
scanf("%d %d %d",&n,&f,&m);
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
dis[i][j]=inf;
}
dis[i][i]=0;
}//预处理。
for(int i=1;i<=f;i++){
scanf("%d",&like[i]);
}//输入每个喜欢的牧场
for(int i=1;i<=m;i++){
scanf("%d %d %d",&u,&v,&t);
dis[u][v]=t;
dis[v][u]=t;
}//输入牧场距离并预处理
for(int k=1;k<=n;k++){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);//裸的floyd板子
}
}
}
int ans,maxx=inf,sum=0;
for(int i=1;i<=n;i++){
sum=0;
for(int j=1;j<=f;j++){
sum+=dis[i][like[j]];//统计从该节点到所有喜欢的牧场的总最短距离
}
if(sum<maxx){
ans=i;
maxx=sum;
}
//这里注意一下，题目说让我们求的是平均距离最小，但其实喜欢的牧场个数固定，我们就只需要求总最短路径最小就行了，不用再取平均值。
}
cout<<ans;//输出牧场序号
return 0;
}
拓展延伸：算法变形
floyd算法在一些情况下可以变形，用途是判断图上任意两点间连通性。
伪代码：
#define maxn 最大节点数
bool val[maxn][maxn];
bool dis[maxn][maxn];
inline void floyd(){
for(int i=1;i<=maxn;i++)
for(int j=1;j<=maxn;j++)
if(val[i][j])
dis[i][j]=1;//相邻两点间距离设为ture
else
dis[i][j]=0;//不相邻设为false
for(int k=1;k<=maxn;k++)
for(int i=1;i<=maxn;i++)
for(int j=1;j<=maxn;j++)
dis[i][j]=dis[i][j]||(dis[i][k]&&dis[k][j]);
//原理：若i与k联通，k与j联通，则i与j联通
}
完结撒花