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算法，等看懂了在寫一下。