任意两点间的最短路问题 Floyd-Warshall算法

这一算法与之前的Bellman-F=Ford算法一样，都可以判断负环

只需要检查dp [i] [j] 是负数的顶点i即可

// 求解任意两点间的最短路径问题
// Floyed-Warshall算法
// 复杂度O(N^3),N为顶点数

#include <cstdio>
#include <iostream>

using namespace std;
// 用dp的思路来求解
// dp[k][i][j]:从i到j，只利用前K个节点的最短路
// dp[k][i][j]=dp[k-1][i][k] + dp[k-1][k][j]
// 由于后一层所需的，都来自前一层，而前一层所需
// 然后在考虑循环顺序，定k，并且维护最小，所以中间元素必定使用之前维护的在k行k列的元素
// 而维护最小值时，k行k列元素，在循环中，加和一定大于原来的值（否则存在d[i][j]<0,存在负圈)
// 所以维护最小值时不更新，依旧是上一列表中的值
// 所以dp数组可以降维进行运算

const int max_N = 200+2;
const int max_E = 10000+2;
const int INF = 1e9;

int dp[max_N][max_N];
int N,E;

void floyd_warshall()
{
    for(int k=0;k<N;++k)
    {
        for(int i=0;i<N;++i)
        {
            for(int j=0;j<N;++j)
            {
                dp[i][j]=min( dp[i][j],dp[i][k]+dp[k][j] );
            }
        }
    }
}

int main()
{
    scanf("%d %d",&N,&E);
    int a,b,c;
    for(int i=0;i<N;++i)
    {
        for(int j=0;j<N;++j)
        {
            if(i==j)
            {
                dp[i][j]=0;
            }
            else
            {
                dp[i][j]=INF;
            }
        }
    }
    for(int i=0;i<E;++i)
    {
        scanf("%d %d %d",&a,&b,&c);
        dp[a][b]=c;
        // 无向图
        dp[b][a]=c;
    }
    floyd_warshall();

    for(int i=0;i<N;++i)
    {
        for(int j=0;j<N;++j)
        {
            printf("%d ",dp[i][j]);
        }
        printf("
");
    }
    return 0;
}
/*
7 10
0 1 2
0 2 5
1 2 4
1 3 6
1 4 10
2 3 2
3 5 1
4 5 3
4 6 5
5 6 9




0 2 5 7 11 8 16
2 0 4 6 10 7 15
5 4 0 2 6 3 11
7 6 2 0 4 1 9
11 10 6 4 0 3 5
8 7 3 1 3 0 8
16 15 11 9 5 8 0
*/