FLoyd算法的扩展
安昙
2018-07-17 10:05:20
Floyd算法是一种求任意点到任意点的最短距离。可以求边权为负值，有向图、无向图等的最短路径。但是边权可以有负权值的边，但不能有包含负权值边组成的回路，不然算出来的就不是正确答案！！这个算法效率很低可以说是暴力。但是这种暴力是带着动态规划的暴力！！但是却不能有边权和为负值的回路
上代码
------------
```cpp
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define Inf 1<<29
int mp[100][100];
int n,m;
int main(){
while(~scanf("%d%d",&n,&m)){//代表有n个节点 m 条权值边
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(i!=j){//初始化默认距离表示i节点到j节点的距离。节点相同距离为0
mp[i][j]=Inf;
}else{
mp[i][j]=0;
}
}
}
int a,b,c;
for(int i=1;i<=m;i++){
scanf("%d%d%d",&a,&b,&c);
mp[a][b]=c;
// mp[b][a]=c;//写上这个就是无向图
}
for(int k=1;k<=n;k++){//主要代码实现区，可以模拟一下。关键是模拟，然后自己再想为什么。。
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(i!=j&&j!=k){
mp[i][j]=min(mp[i][j],mp[i][k]+mp[k][j]);
}
}
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){//在这里输出任意点到任意点的距离
printf("dis %d %d = %d\n",i,j,mp[i][j]);
}
}
}
return 0;
}
```