最短路之Floyd算法
程序员文章站
2024-03-16 13:03:40
...
Floyd算法不能判断负环
算法思路
判断是否可以通过中转点 k 使 i 到 j 的距离减小
如图
设i-j为100
i-k为40
k-j为40
显然通过k的中转 从i到j所耗费的路程变短了
#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define mod 1000000007
#define IOS ios::sync_with_stdio(false)
#define endl '\n'
using namespace std;
typedef long long ll;
const int maxn = 205;
int n, m, mat[maxn][maxn];
int main() {
while (scanf("%d%d", &n, &m) != EOF) {
for (int i = 0;i < n;++i) {//初始化邻接矩阵
for (int j = 0;j < n;++j) {
if (i == j)mat[i][j] = 0;//自己到自己的距离为0
else mat[i][j] = INF;
}
}
for (int i = 0;i < m;++i) {
int x, y, z;
scanf("%d%d%d", &x, &y, &z);//读入每条边
mat[x][y] = min(mat[x][y], z);//无向图所以需要读入两次
mat[y][x] = min(mat[y][x], z);//读入过程维护最小值
}
int s, t;
scanf("%d%d", &s, &t);
for (int k = 0;k < n;++k)//用中继点中转
for (int i = 0;i < n;++i)
for (int j = 0;j < n;++j)
mat[i][j] = min(mat[i][j], mat[i][k] + mat[k][j]);//i直接到j的距离是否比i到k+k到j的距离大
//若是 则更新最小值 此外 每个顶点都有可能使i到j的距离变小 所以需要遍历每个顶点(k)
if (mat[s][t] == INF)cout << -1 << endl;//如果为INF说明 s到t不通
else printf("%d\n", mat[s][t]);
}
return 0;
}
上一篇: JAVA算法:零钱兑换问题求解