Bellman-Ford算法

1、时间复杂度：O(V*E);  V--->顶点数、E--->边数

2、优点：可以处理负权值的情况，实现简单

3、最多进行V-1次松弛，因为要对所有的点进行遍历松弛，起点可以除外

4、主要用于存在负权值的图中（没有也可以，只是效率低）；也可以判断图中是否存在环（在进行了V-1次遍历松弛后，再进行一次遍历，若最短路还能更新，则证明有环）

//对每个顶点进行松弛（即遍历求最短路），除起点外共需进行V-1次
//此代码为无向图(有向图只需把初始化e的那几条语句改动一下就好，即去掉一个方向)
#include
#include
#include
using namespace std;
const int NUM = 1005;

struct Node
{
    
    int u,v,wei;//起点、终点、边权
};

int flag = 0;
vector e;
//int edge[NUM][NUM];//edge[i][j]:边i->j的权值
int dis[NUM];//dis[i]:从起点到顶点i的最短路径
int V,E;//顶点个数；边数

void bf(int st)//st:起点
{
    memset(dis,0x3f3f,sizeof dis);
    dis[st] = 0;//起点到其本身为0
    //开始松弛
    for(int i=1;i<=V-1;i++)
    {
        for(int j=0;jdis[u]+w)
                dis[v] = dis[u]+w;
        }
    }

    for(int i=0;idis[u]+w)
        {
            dis[v] = dis[u]+w;
            flag = 1;//还有更新说明有环
        }    
    }
}

int main()
{
    cin >> V >> E;
    int u,v,w;
    for(int i=0;i> u >> v >> w;
        e.push_back({u,v,w});
        e.push_back({v,u,w});
        //edge[u][v] = w;
        //edge[v][u] = w;
    }
    bf(1);
    int n;//假设到顶点n,也可以通过键盘输入
    n = V;//假设顶点按照序号来
    if(flag) cout<<"No the shortest route"<