Bellman-Ford算法及SPFA算法

Bellman-Ford算法

Bellman-Ford算法能解决存在负权边的单源点最短路径问题。

bool Bellman_Ford(){
    bool f;
    for(int i = 0; i < n; i++){
        f = false;
        for(int j = 0; j < m; j++){
            int x = edge[j].from;
            int y = edge[j].to;
            int z = edge[j].v;
            if(dis[x] + z < dis[y]){
                dis[y] = dis[x] + z;
                f = true;
            }
        }
        if(!f) break;
    	if(i == n - 1 && f) return false;  //表示图中存在负权环(因为从源点出发到n-1个结点，而n-1遍还没有更新完毕)
    }
    return true;  //表示找到了最短路
}

几点解释：

m是什么？ 图中一共有m条边。

为什么松弛的过程要循环n次？ 因为在进行了一次寻找可松弛边的循环（我们暂且将它称为m循环）后，结果只有两种情况。

第一种情况：没找到可松弛边，此时 f 仍旧等于 false，n循环直接break了；

第二种情况：找到了可松弛边。无论在第一轮m循环中松弛了多少次，总会有一次松弛得到的是源点到目标点的最短距离，否则就出现负权环了。此时按照这种最坏假设，循环 n-1 次就一定可以使 n-1 个点都找到各自到源点的最短路径。

SPFA算法

SPFA (shortest path faster algorithm) 是Bellman-Ford算法的一种队列实现，减少了不必要的冗余计算。(SPFA是Bellman-Ford的优化)

Bellman-Ford算法的复杂度较高，中间进行了一些不必要的计算，因为并不是每个顶点都会在松弛操作中改变。SPFA算法在最坏情况下的复杂度很高，但是在正常情况下点的平均入队次数不大于2。

Bellman-Ford能实现的，都可以用SPFA来解决，所以一般都会用SPFA。

基本思想是：使用队列，初始时队列里只有源点，dis 记录源点到所有点的最短路径 (初始时为无穷，若源点为s，则 dis[s] = 0。除了起点赋值为0外，其他顶点的对应的dis的值都赋予无穷大，这样有利于后续的松弛)，然后用队列里的点更新 dis 数组的值，如果某点的 dis 值被更新，则将该点加入到队尾。重复执行直到队列为空。

如果存在一点进入队列的次数大于等于 n 次，则存在负权环。(当图中有负权环时，队列就不会有空的情况了，因为由于负权环的存在，负权环上的点就可以一直被松弛，一直能被松弛就代表着队列会不断反复让负权环上的点入队出队，程序就会死循环)

bool spfa(){  //SPFA判断负权环
    for(int i = 0; i != top; i++){
        int x = q[i];  //取队列元素，数组q模拟队列
        have[x] = 0;  //出队，have[x] = 0 表示x已经不在队列中
        for(int j = 0; j < head[x].size(); j++){
            y = head[x][j].to;
            z = head[x][j].v;
            if(dis[x] + z < dis[y]){
                dis[y] = dis[x] + z;
                if(!have[y]){  //如果y不在队列中
                    have[y] = 1;  //将y入队
                    q[top++] = y;  //加到队尾
                    cnt[y]++;  //记录结点y入队次数
                    if(cnt[y] >= n)  //存在负权环
                        return true;
                }
            }
        }
    }
    return false;  //不存在负权环
}

关于SPFA的一篇很详细的博客：

https://blog.csdn.net/qq_35644234/article/details/61614581