欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

最短路之Floyd算法

程序员文章站 2024-03-16 13:03:40
...

Floyd算法不能判断负环
算法思路
判断是否可以通过中转点 k 使 ij 的距离减小
如图
最短路之Floyd算法
设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;
 }
相关标签: 学习收藏