Bellman-Ford（最短路）

bellmen-ford算法，与dijkstra不同，bellman-ford可以运用于有负权值的图，不过复杂度很高，O(N*M )… 慎用~（可以用SPFA，它bwllman-ford的扩展）

Bellman-ford算法同样是对每条边进行N-1次松弛，当有权值为负时，对所有边进行N-1次松弛，如果dis还能更新，说明有负环。

ps：名词解释【负环】 在一个图里每条边都有一个权值（有正有负)

如果存在一个环（从某个点出发又回到自己的路径），而且这个环上所有权值之和是负数，那这就是一个负权环，也叫负权回路

存在负权回路的图是不能求两点间最短路的，因为只要在负权回路上不断兜圈子，所得的最短路长度可以任意小。

Bellman-ford原理：

1.如果最短路存在，则每个顶点最多经过一次，因此不超过n-1条边；

2.长度为k的路由长度为k-1的路加一条边得到；

3.由最优性原理，只需依次考虑长度为1，2，…，k-1的最短路。

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
int inf=;
int main()
{
    int i,k,n,m;
    int u[],v[],w[],dis[];
    scanf("%d%d",&n,&m);
    for(i=; i<=n; i++)
        scanf("%d%d%d",&u[i],&v[i],&w[i]); 
    for(i=; i<=n; i++)
        dis[i]=inf;
    dis[]=;
    int flag;
    for(k=; k<n; k++)
    {
        flag=; //标记dis数组会不会变化
        //进行一轮松弛
        for(i=; i<=m; i++)
        {
            if(dis[v[i]]>dis[u[i]]+w[i]) //表示u[i]->v[i]这条边的值+1号顶点到u[i]点的值是否小于原来1号顶点到u[i]点的值
            {
                dis[v[i]]=dis[u[i]]+w[i];
                flag=;//dis数组更新
            }
        }
        if(flag==) break; //表示数组松弛完毕
    }
    flag=; //检验是否会出现负环
    for(i=; i<=m; i++)
        if(dis[v[i]]>dis[u[i]]+w[i]) flag=; //若还能松弛则存在负环
    if(flag==)
    {
        for(i=; i<=n; i++)
            printf("%d ",dis[i]);
        printf("\n");
    }
    else
        printf("此图存在负环回路\n");

    return ;
}
           

Bellman-Ford 算法往往不到n-1轮就已经松弛完毕，用标记变量可以减少循环次数。

在这个算法中加入队列进行优化就是SPFA算法，等看懂了在写一下。