单源最短路径之Bellman-Ford算法

之前文章对于Dijkstra算法进行了讲解和实现，其实现的原理在于采用贪心算法，遍历N(结点数)次，每次找到局部最优的路径的结点u， 判断该节点可达的顶点v的权重是否大于结点u权重+u->v的权重，如果大于则替换顶点v的权重(也叫松弛操作)。因为Dijkstra算法无法 正确计算负权路径的最短路径(详情可看上一节)，所以有了Bellman-Ford算法来解决这一问题。

贝尔曼-福特算法

贝尔曼-福特算法（Bellman-Ford）是由理查德·贝尔曼（Richard Bellman） 和 莱斯特·福特 创立的，求解单源最短路径问题的一种算法。有时候这种算法也被称为 Moore-Bellman-Ford 算法，因为 Edward F. Moore 也为这个算法的发展做出了贡献。它的原理是对图进行V-1次松弛操作(V是顶点数量)，得到所有可能的最短路径。其优于Dijkstra算法的方面是边的权值可以为负数、实现简单，缺点是时间复杂度过高，高达O(VE)。但算法可以进行若干种优化，提高了效率。

贝尔曼-福特算法与迪科斯彻算法类似，都以松弛操作为基础，即估计的最短路径值渐渐地被更加准确的值替代，直至得到最优解。在两个算法中，计算时每个边之间的估计距离值都比真实值大，并且被新找到路径的最小长度替代。然而，迪科斯彻算法以贪心法选取未被处理的具有最小权值的节点，然后对其出边进行松弛操作；而贝尔曼-福特算法简单地对所有边进行松弛操作，共V-1次，其中V是图的顶点数量。在重复的计算中，已计算得到正确的距离的边的数量不断增加，直到所有边都计算得到了正确的路径。这样的策略使得贝尔曼-福特算法比迪科斯彻算法适用于更多种类的输入

实现过程

从上面介绍我们可以知道，Bellman算法对每一条边采用松弛操作，对于单源最短路径实现来说， 源点到某一顶点所经过的边最多为V-1条(可以看成树的两个结点)，如下，三个顶点ABC，A->C最多走过2两条边即A->B->C

A->B
A->C
B->C

在我们将源点最短路径设置为0时，每次松弛操作，至少会松弛一条边，而最多共有N-1条边，所以我们需要遍历N-1次。每一次遍历的松弛操作和Dijkstra算法类似，判断结点u权重是否大于 v->u的权重+v的权重。

与Dijkstra算法使用最短边向其他顶点扩展方案不同，在Bellman-Ford算法中松弛操作是针对边，其目的是对每一条边进行松弛， 这样总能使得边达到最小，如下图解，A为源点

A->C 2

D->C 1

A->B -1

B->D 1

上面共计 4个顶点，源点A到达任意顶点B，C，D最高走V-1=3条边，也就是松弛3轮， 初始化时源点A到任意顶点设置为无穷大，s[]表示最短距离，S[A]=0。

那么第一轮:

A -> C 边权2 可以推导==> (S[C] = ∞) > (S[A] + W[AB] = 0+2)条件符合，所以进行松弛操作 S[C] = 2

D -> C 边权1 可以推导==> (S[C] = 2) > (S[D] + W[DC] = ∞+1)条件不符合，无法进行松弛操作

A -> B 边权-1 可以推导==> (S[B] = ∞) > (S[A] + W[AB] = 0+(-1))条件符合，所以进行松弛操作 S[B] = -1

B -> D 边权1 可以推导==> (S[D] = ∞) > (S[B] + W[BD] = -1+1)条件符合，所以进行松弛操作 S[D] = 0

然后进行第二轮(基于第一轮):

A -> C 边权2 可以推导==> (S[C] = 2) > (S[A] + W[AB] = 0+2)条件不符合，无法进行松弛操作

D -> C 边权1 可以推导==> (S[C] = 2) > (S[D] + W[DC] = 0+1)条件符合，所以进行松弛操作 S[C] = 1

A -> B 边权-1 可以推导==> (S[B] = -1) > (S[A] + W[AB] = 0+(-1))条件不符合，无法进行松弛操作

B -> D 边权1 可以推导==> (S[D] = 0) > (S[B] + W[BD] = -1+1)条件不符合，无法进行松弛操作

第三轮逻辑同上。

我们会发现其实第二轮的时候，已经实现最短路径了，第三轮属于没有用的遍历。

负环

负环,又叫负权回路,负权环,指的是一个图中存在一个环,里面包含的边的边权总和<0。在存在负环的图中,是求不出最短路径的， 因为每次要在这个环上遍历，最短路径就会无限次的变小。如下

A->B 1
A->C 1
C->B -1
B->D 1
D->C 1

那么BCD就会存在负环，按照上面N-1次遍历后，我们再遍历，最短路径仍会变小。

实现代码(C++)

//
//  main.cpp
//  Bellman-Ford
//
//  Created by 陈龙.
//  Copyright © 2019 陈龙. All rights reserved.
//

#include <iostream>

using namespace std;

//顶点和边和源点
int N,E,S;

 struct Graph{
    //起点，终点
    int u,v;
    int w;
//    Graph(int _u,int _v,int _w):u(_u),v(_v),w(_w){};
};



int main(int argc, const char * argv[]) {
    // insert code here...
    cin>>N>>E>>S;
    Graph g[N];
    int dis[N];
    int u,v,w;
    for (int i=0; i<E; i++) {
        cin>>u>>v>>w;
        g[i].u = u;
        g[i].v=v;
        g[i].w=w;
    }
    //初始化
    dis[S] = 0;
    for(int i=0;i<E;i++){
        if (i!=S) {
           dis[i] = INT_MAX;
        }
    }

    //两顶点最多N-1条边
    for (int i=0; i<N-1; i++) {
        for (int j=0; j<E; j++) {
            if (dis[g[j].v]> g[j].w + dis[g[j].u]) {
                dis[g[j].v] =g[j].w + dis[g[j].u];
            }
        }
    }
    // 判断是否有负环路
    for(int i=0; i<E; ++i){
        if(dis[g[i].v] > dis[g[i].u] + g[i].w){
               cout<<"有负环路"<<endl;
               break;
           }
        }
    
    for(int i=0;i<N;i++){
        cout<<dis[i]<<endl;
    }

    return 0;
}

    /*
     eg1:
     6 7 0
     0 1 -1
     0 2 2
     1 3 2
     2 3 -4
     2 4 -3
     4 5 5
     3 5 2
     eg2:
     3 3 0
     0 1 1
     0 2 2
     1 2 -1
     eg3
     3 4 1
     0 1 1
     2 0 1
     1 2 -1
     2 1 -2
     */