最短路径之Bellman_Ford

女爷i 2022-06-11 07:47 92阅读 0赞

适用于：

单源最短路径(从源点s到其它所有顶点v);

有向图&无向图(无向图可以看作(u,v),(v,u)同属于边集E的有向图);

边权可正可负(如有负权回路输出错误提示);

差分约束系统;

**Bellman-Ford算法的流程如下：**  
给定图G(V, E)（其中V、E分别为图G的顶点集与边集），源点s，数组Distant\[i\]记录从源点s到顶点i的路径长度，初始化数组Distant\[n\]为inf, Distant\[s\]为0；

以下操作循环执行至多n-1次，n为顶点数：  
对于每一条边e(u, v)，如果Distant\[u\] + w(u, v) < Distant\[v\]，则另Distant\[v\] = Distant\[u\]+w(u, v)。w(u, v)为边e(u,v)的权值；  
若上述操作没有对Distant进行更新，说明最短路径已经查找完毕，或者部分点不可达，跳出循环。否则执行下次循环；

为了检测图中是否存在负环路，即权值之和小于0的环路。对于每一条边e(u, v)，如果存在Distant\[u\] + w(u, v) < Distant\[v\]的边，则图中存在负环路，即是说改图无法求出单源最短路径。否则数组Distant\[n\]中记录的就是源点s到各顶点的最短路径长度。

可知，Bellman-Ford算法寻找单源最短路径的时间复杂度为O(V\*E).

**Bellman－Ford算法可以大致分为三个部分**  
第一，初始化所有点。每一个点保存一个值，表示从原点到达这个点的距离，将原点的值设为0，其它的点的值设为无穷大（表示不可达）。  
第二，进行循环，循环下标为从1到n－1（n等于图中点的个数）。在循环内部，遍历所有的边，进行松弛计算。  
第三，遍历途中所有的边（edge（u，v）），判断是否存在这样情况：  
d（v） > d (u) + w(u,v)  
则返回false，表示途中存在从源点可达的权为负的回路。  
   
之所以需要第三部分的原因，是因为，如果存在从源点可达的权为负的回路。则 应为无法收敛而导致不能求出最短路径。

但是要注意有的题目会有重复的边，比如这个题：[Til the Cows Come Home][]  题解：[点击打开链接][Link 1]

bool Bellman_Ford()  
    {  
        for(int i = 1; i <= nodenum; ++i) //初始化  
            dis[i] = (i == original ? 0 : MAX);  
        for(int i = 1; i <= nodenum - 1; ++i)  
            for(int j = 1; j <= edgenum; ++j)  
                if(dis[edge[j].v] > dis[edge[j].u] + edge[j].cost) //松弛
                {  
                    dis[edge[j].v] = dis[edge[j].u] + edge[j].cost;  
                }  
                bool flag = 1; //判断是否含有负权回路  
                for(int i = 1; i <= edgenum; ++i)  
                    if(dis[edge[i].v] > dis[edge[i].u] + edge[i].cost)  
                    {  
                        flag = 0;  
                        break;  
                    }  
                    return flag;  
    }

#include <iostream>
    using namespace std;
    const int maxnum = 100;
    const int maxint = 99999;
     
    // 边，
    typedef struct Edge{
        int u, v;    // 起点，重点
        int weight;  // 边的权值
    }Edge;
     
    Edge edge[maxnum];     // 保存边的值
    int  dist[maxnum];     // 结点到源点最小距离
     
    int nodenum, edgenum, source;    // 结点数，边数，源点
     
    // 初始化图
    void init()
    {
        // 输入结点数，边数，源点
        cin >> nodenum >> edgenum >> source;
        for(int i=1; i<=nodenum; ++i)
            dist[i] = maxint;
        dist[source] = 0;
        for(int i=1; i<=edgenum; ++i)
        {
            cin >> edge[i].u >> edge[i].v >> edge[i].weight;
            if(edge[i].u == source)          //注意这里设置初始情况
                dist[edge[i].v] = edge[i].weight;
        }
    }
     
    // 松弛计算
    void relax(int u, int v, int weight)
    {
        if(dist[v] > dist[u] + weight)
            dist[v] = dist[u] + weight;
    }
     
    bool Bellman_Ford()
    {
        for(int i=1; i<=nodenum-1; ++i)
            for(int j=1; j<=edgenum; ++j)
                relax(edge[j].u, edge[j].v, edge[j].weight);
        bool flag = 1;
        // 判断是否有负环路
        for(int i=1; i<=edgenum; ++i)
            if(dist[edge[i].v] > dist[edge[i].u] + edge[i].weight)
            {
                flag = 0;
                break;
            }
        return flag;
    }
    int main()
    {
        //freopen("input3.txt", "r", stdin);
        init();
        if(Bellman_Ford())
            for(int i = 1 ;i <= nodenum; i++)
                cout << dist[i] << endl;
        return 0;
    }

[Til the Cows Come Home]: http://poj.org/problem?id=2387
[Link 1]: http://blog.csdn.net/kangyan__/article/details/76587323