[算法系列之二十九]Bellman-Ford最短路径算法

た入场券 2023-06-23 07:52 10阅读 0赞

**单源最短路径**

给定一个图,和一个源顶点src,找到从src到其它所有所有顶点的最短路径，图中可能含有负权值的边。

Dijksra的算法是一个贪婪算法,时间复杂度是O(VLogV)(使用最小堆)。但是迪杰斯特拉算法在有负权值边的图中不适用,Bellman-Ford适合这样的图。在网络路由中，该算法会被用作距离向量路由算法。

Bellman-Ford也比迪杰斯特拉算法更简单和同时也适用于分布式系统。但Bellman-Ford的**时间复杂度是O(VE)**,这要比迪杰斯特拉算法慢。（V为顶点的个数,E为边的个数）

**算法描述**

输入:图 和 源顶点src   
输出:从src到所有顶点的最短距离。如果有负权回路(不是负权值的边),则不计算该最短距离，没有意义，因为可以穿越负权回路任意次，则最终为负无穷。

**算法步骤**

1.初始化：将除源点外的所有顶点的最短距离估计值 dist\[v\] ← +∞, dist\[s\] ←0;   
2.迭代求解：反复对边集E中的每条边进行松弛操作，使得顶点集V中的每个顶点v的最短距离估计值逐步逼近其最短距离；（运行|v|-1次）   
3.检验负权回路：判断边集E中的每一条边的两个端点是否收敛。如果存在未收敛的顶点，则算法返回false，表明问题无解；否则算法返回true，并且从源点可达的顶点v的最短距离保存在 dist\[v\]中。

关于该算法的证明也比较简单，采用反证法，具体参考：[http://courses.csail.mit.edu/6.006/spring11/lectures/lec15.pdf][http_courses.csail.mit.edu_6.006_spring11_lectures_lec15.pdf]   
该算法是利用**动态规划**的思想。该算法以自底向上的方式计算最短路径。   
它首先计算最多一条边时的最短路径(对于所有顶点)。然后,计算最多两条边时的最短路径。外层循环需要执行|V|-1次。

**例子**

一下面的有向图为例：给定源顶点是0，初始化源顶点距离所有的顶点都是是无穷大的,除了源顶点本身。因为有5个顶点，因此所有的边需要处理4次。

![这里写图片描述][20150423150946160]

按照以下的顺序处理所有的边：(B,E), (D,B), (B,D), (A,B), (A,C), (D,C), (B,C), (E,D).   
第一次迭代得到如下的结果(第一行为初始化情况,最后一行为最终结果)：

当 (B,E), (D,B), (B,D) 和 (A,B) 处理完后，得到的是第二行的结果。   
当 (A,C) 处理完后，得到的是第三行的结果。   
当 (D,C), (B,C) 和 (E,D) 处理完后，得到第四行的结果。

![这里写图片描述][20150423151138845]

第一次迭代保证给所有最短路径最多只有1条边。当所有的边被第二次处理后，得到如下的结果(最后一行为最终结果)：

![这里写图片描述][20150423151048295]

第二次迭代保证给所有最短路径最多只有2条边。我们还需要2次迭代(即所谓的松弛操作)，就可以得到最终结果。

**代码**

/*-------------------------------------
    *   日期：2015-04-22
    *   作者：SJF0115
    *   题目: Bellman-Ford算法(单源最短路径)
    *   博客：
    ------------------------------------*/
    #include <iostream>
    using namespace std;
    
    //表示一条边
    struct Edge{
        // 起点
        int src;
        // 终点
        int dest;
        // 权重
        int weight;
    };
    //带权值的有向图
    struct Graph{
        // 顶点的数量
        int V;
        // 边的数量
        int E;
        // 用边的集合 表示一个图
        Edge* edge;
    };
    // 创建图
    Graph* CreateGraph(int v,int e){
        Graph* graph = (Graph*)malloc(sizeof(Graph));
        graph->E = e;
        graph->V = v;
        graph->edge = (Edge*)malloc(e*sizeof(Edge));
        return graph;
    }
    // 打印结果
    void Print(int dist[],int n){
        cout<<"单源最短路径:"<<endl;
        for(int i = 0;i < n;++i){
            if(dist[i] == INT_MAX){
                cout<<"与节点"<<i<<"距离->无穷大"<<endl;
            }//if
            else{
                cout<<"与节点"<<i<<"距离->"<<dist[i]<<endl;
            }
        }//for
    }
    // 单源最短路径
    bool BellmanFord(Graph* graph,int src){
        int v = graph->V;
        int e = graph->E;
        // 存储距离
        int dist[v];
        // 初始化
        for(int i = 0;i < v;++i){
            dist[i] = INT_MAX;
        }//for
        dist[src] = 0;
        // v-1次操作
        Edge edge;
        int a,b,weight;
        for(int i = 1;i < v;++i){
            // 对e条边进行松弛
            for(int j = 0;j < e;++j){
                edge = graph->edge[j];
                a = edge.src;
                b = edge.dest;
                weight = edge.weight;
                if(dist[a] != INT_MAX && dist[a]+weight < dist[b]){
                    dist[b] = dist[a]+weight;
                }//if
            }//for
        }//for
        // 检测负权回路
        bool isBack = false;
        for(int i = 0;i < e;++i){
            edge = graph->edge[i];
            a = edge.src;
            b = edge.dest;
            weight = edge.weight;
            if(dist[a] != INT_MAX && dist[a]+weight < dist[b]){
                isBack = true;
                break;
            }//if
        }//for
        // 打印结果
        Print(dist,v);
        return isBack;
    }
    
    int main(){
        int v = 7;
        int e = 9;
    
        Graph* graph = CreateGraph(v,e);
    
        graph->edge[0].src = 0;
        graph->edge[0].dest = 1;
        graph->edge[0].weight = -1;
    
        graph->edge[1].src = 0;
        graph->edge[1].dest = 2;
        graph->edge[1].weight = 4;
    
        graph->edge[2].src = 1;
        graph->edge[2].dest = 2;
        graph->edge[2].weight = 3;
    
        graph->edge[3].src = 1;
        graph->edge[3].dest = 3;
        graph->edge[3].weight = 2;
    
        graph->edge[4].src = 1;
        graph->edge[4].dest = 4;
        graph->edge[4].weight = 2;
    
        graph->edge[5].src = 3;
        graph->edge[5].dest = 2;
        graph->edge[5].weight = 5;
    
        graph->edge[6].src = 3;
        graph->edge[6].dest = 1;
        graph->edge[6].weight = 1;
    
        graph->edge[7].src = 4;
        graph->edge[7].dest = 3;
        graph->edge[7].weight = -3;
    
        graph->edge[8].src = 5;
        graph->edge[8].dest = 6;
        graph->edge[8].weight = 2;
    
        bool result = BellmanFord(graph,0);
        if(result){
            cout<<"图中存在回路"<<endl;
        }//if
        else{
            cout<<"图中不存在回路"<<endl;
        }//else
        return 0;
    }

转载于：[Bellman-Ford最短路径算法][Bellman-Ford]

本文原文地址： [https://blog.csdn.net/SunnyYoona/article/details/45222073][https_blog.csdn.net_SunnyYoona_article_details_45222073]

[http_courses.csail.mit.edu_6.006_spring11_lectures_lec15.pdf]: http://courses.csail.mit.edu/6.006/spring11/lectures/lec15.pdf
[20150423150946160]: https://img-blog.csdn.net/20150423150946160
[20150423151138845]: https://img-blog.csdn.net/20150423151138845
[20150423151048295]: https://img-blog.csdn.net/20150423151048295
[Bellman-Ford]: http://www.acmerblog.com/bellman-ford-algorithm-5828.html
[https_blog.csdn.net_SunnyYoona_article_details_45222073]: https://blog.csdn.net/SunnyYoona/article/details/45222073