Bellman-Ford算法--解决负权边的单源最短路径算法

ゞ浴缸里的玫瑰 2022-07-12 02:43 199阅读 0赞

在[http://blog.csdn.net/hacker\_zhidian/article/details/54915152][http_blog.csdn.net_hacker_zhidian_article_details_54915152]这篇博客中，我们用Dijkstra算法单源最短路径，但是Dijkstra算法对于存在负权边的图就无能为力了，接下来就是Bellman-Ford算法显威的时候了，因为它能解决存在负权边的图中的单源最短路径问题。Bellman-Ford算法的核心思想是：对图中所有的边进行缩放，每一次缩放更新单源最短路径。  
我们依然通过一个例子来看：  
![这里写图片描述][SouthEast]  
假设存在这么一个有向图。图中有A 、B、C、D、E 五个顶点，有 A–>B（3）、A–>E（-2）、B–>D（5）、B–>C（2）、D–>C（1）、D–>E（4）这 6 条边。假设现在我们要求顶点A到其他顶点的最短路径，按照Bellman-Ford算法的思想：

**我们要对所有的边进行“缩放”，首先找到第一条边：A–>B（3），那么对于顶点B，能不能通过顶点B使得顶点A到其他顶点的最短路径变短呢，在这里我们可以找到A–>B（3）来使得顶点A到顶点B的最短路径变短，于是我们更新顶点A到顶点B的最短路径。接下来我们再找第二条边，同样的A–>E（-2）可以使得顶点A到顶点E的最短路径变短，继续更新顶点A到顶点E的最短路径。重复刚刚的缩放过程。。。将所有的边缩放完了之后，重复上面的缩放过程。那么什么时候缩放结束呢。最多在缩放了n-1轮（n为图中顶点的总数）的时候就结束了（因为图中两个顶点中的边最多有n-1条）。**

其实Bellman-Ford算法和Dijkstra算法类似，都是缩放使得最短路径变短，不同的是Dijkstra算法是对顶点进行缩放，Bellman-Ford算法是对边进行缩放。  
既然是对边进行缩放，那么我们就要储存边的信息，这里可以采用一个结构体数组来储存边的信息。  
下面是Bellman-Ford算法的核心代码：

for(int i = 1; i <= n - 1; i++) // 最多n - 1轮缩放
    {
        for(int j = 1; j <= m; j++) // 每一轮对所有的边进行缩放
        {
            if(dis[edge[j].end] > dis[edge[j].start] + edge[j].weight) //edge是储存边的信息的结构体
            {
                dis[edge[j].end] = dis[edge[j].start] + edge[j].weight; // 如果这条边能够使得顶点A到这条边结束的那个顶点的最短路径变短，则更新最短路径
            }
        }
    }

理解了这个，下面就是简单的收尾了，这里给出案例的完整代码：

#include <iostream>
    using namespace std;
    const int N = 500;  // 图中最多有500个顶点
    const int inf = 999999999;  // 无穷大，表示源点到其他顶点的初始最短路径
    
    struct Edge // 储存边的信息的结构体
    {
        int start;  // 边的开始顶点
        int end;    // 边的结束顶点
        int weight; // 边的权值
    };
    Edge edge[N*N]; // 最多250000条边
    int dis[N]; // 储存源点到其他顶点的最短路径的数组
    
    
    int main()
    {
        int n, m, s;    // 图中顶点的总数，边的总数和源点
        cin >> n >> m >> s;
        for(int i = 1; i <= m; i++) // 输入图中边的信息
        {
            cin >> edge[i].start >> edge[i].end >> edge[i].weight;
        }
        for(int i = 1; i <= n; i++)
        {
            dis[i] = inf;   // 初始化源点到其他顶点的最短路径
        }
        dis[s] = 0;
    
        // Bellman-Ford算法的核心代码：
        for(int i = 1; i <= n - 1; i++) // 最多n - 1轮缩放
        {
            int check = 0;
            for(int j = 1; j <= m; j++) // 每一轮对所有的边进行缩放
            {
                if(dis[edge[j].end] > dis[edge[j].start] + edge[j].weight) //edge是储存边的信息的结构体
                {
                    dis[edge[j].end] = dis[edge[j].start] + edge[j].weight; // 如果这条边能够使得源点到这条边结束的那个顶点的最短路径变短，则更新最短路径
                    check = 1;
                }
            }
            if(check == 0)  
            {
                break;  // 如果这一轮的缩放没有使得任何顶点到源点的最短路径变短，那么就不用尝试下一轮缩放了，因为下一轮缩放和这一轮缩放的原理和步骤是一样的
            }
        }
    
        for(int i = 1; i <= n; i++) //输出结果
        {
            cout << dis[i] << " ";
        }
        cout << endl;
    
        return 0;
    }

运行程序，输入数据：  
![这里写图片描述][SouthEast 1]  
带入给定的图中进行检查，确实是我们想要的答案。小伙伴们可以自己尝试一下。  
Bellman-Ford算法的时间复杂度为O(M\*N)，但是我们这里可以对Bellman-Ford算法进行优化：我们每一次缩放的时候如果图中的某条边确实使得源点到其他顶点的最短路径变短，那么下一轮缩放只需要对上一轮缩放的时候使得源点到其他顶点最短路径变短的边的结束点的出边（出度）进行缩放就行了（这句话有点难理解），因为下一轮缩放的原理和这一轮是一样的。我们可以用一个队列来储存这些顶点，缩放的时候将这些顶点依次出队，并且将新的符合要求的顶点入队。直到队列为空。这样的话我们的Bellman-Ford算法在最坏的情况下时间复杂度也是O(M\*N)。

如果博客中有什么不正确的地方，还请多多指点。  
谢谢观看。。。

[http_blog.csdn.net_hacker_zhidian_article_details_54915152]: http://blog.csdn.net/hacker_zhidian/article/details/54915152
[SouthEast]: /images/20220711/1216d10ff1be4ac7bdfa343736dc9d4c.png
[SouthEast 1]: /images/20220711/f98af9158210485eb90fb28ff5844854.png