Bellman_Ford算法 - 解决负权边

1 介绍

这是一个单源最短路径算法，一般计算第1个点到后面的点的最短路径
相区别与Floyd_Warshall算法（参考最简单的最短路径算法 - Floyd_Warshall算法）的是，前者使用n*n的矩阵存储，而这个算法使用三个长n的数组存储，所以前者容易开数组时就爆了
在本人看来，这个算法与Floyd_Warshall算法的本质是一样的，核心都是一个if判断大小后更新为较小值
算法时间复杂度是 : O(NM)

2 代码

#include<iostream>
#include<cstdio>

using namespace std;

int main()
{
    int dis[10],bak[10],n,m,u[10],v[10],w[10],check,flag;
    int inf=99999999;
    cin>>n>>m;
    for(int i=1; i<=m; i++)
        cin>>u[i]>>v[i]>>w[i];
    for(int i=1; i<=n; i++)
        dis[i]=inf;
    dis[1]=0;

    for(int k=1; k<=n-1; k++)   //算法核心
    {
        for(int i=1; i<=n; i++) //备份dis
            bak[i]=dis[i];

        for(int i=1; i<=m; i++) //进行一次松弛，主要就是这里
        {
            if(dis[v[i]]>dis[u[i]]+w[i])
                dis[v[i]]=dis[u[i]]+w[i];
        }

        //检测is数组是否有更新
        check=0;
        for(int i=1; i<=n; i++)
        {
            if(bak[i]!=dis[i])
            {
                check=1;
                break;
            }
        }
        if(check==0)
            break;
    }

    flag=0;
    for(int i=1; i<=m; i++)
        if(dis[v[i]]>dis[u[i]]+w[i])
            flag=1;
    if(flag==1)
        cout<<"此图有复权回路"<<endl;
    else
    {
        for(int i=1; i<=n; i++)
            cout<<dis[i]<<" ";
        cout<<endl;
    }
    return 0;
}
/*
5 5
2 3 2
1 2 -3
1 5 5
4 5 2
3 4 3
*/