【图论——第五讲】Bellman-Ford算法求单源最短路及其队列优化SPFA 算法

ฅ(๑˙o˙๑)ฅ 大家好, 欢迎大家光临我的博客：面向阿尼亚学习
算法学习笔记系列持续更新中~

• 一、前言
• 二、Bellman-Ford算法
• 三、Bellman-Ford算法队列优化SPFA 算法
• 最后

单源最短路，指的是求一个点，到其他所有点的最短距离。即起点是固定的，单一的

注意：最短路问题的核心在于，把问题抽象成一个最短路问题，并建图。图论相关的问题，不侧重于算法原理，而侧重于对问题的抽象。

上篇文章
【图论——第四讲】dijkstra算法求单源最短路及其堆优化提到

所有边的权重都是正数，通常有两种算法

1.朴素Dijkstra
时间复杂度O(n2)，其中n是图中点的个数，m是边的个数
2.堆优化版的Dijkstra
时间复杂度O(mlogn)，其中n是图中点的个数，m是边的个数

如果图存在负边权呢？还能用Dijkstra算法吗？

答案是不可以。

分析：

Dijkstra算法的3个步骤

1、找到当前未标识的且离源点最近的点t
2、对t号点点进行标识
3、用t号点更新其他点的距离

如图：

通过dijkstra算法在图中走出来的最短路径是1 -> 2 -> 4 -> 5，算出 1 号点到 5 号点的最短距离是2 + 2 + 1 = 5，然而还存在一条路径是1 -> 3 -> 4 -> 5，该路径的长度是5 + (-2) + 1 = 4因此存在负边权的图dijkstra 算法失效

dijkstra详细步骤分析

• 初始dist[1] = 0

• 找到了未标识且离源点1最近的结点1，标记1号点，用1号点更新其他所有点的距离，2号点被更新成dist[2] = 2，3号点被更新成dist[3] = 5

• 找到了未标识且离源点1最近的结点2，标识2号点，用2号点更新其他所有点的距离，4号点被更新成dist[4] = 4

• 找到了未标识且离源点1最近的结点4，标识4号点，用4号点更新其他所有点的距离，5号点被更新成dist[5] = 5

• 找到了未标识且离源点1最近的结点3，标识3号点，用3号点更新其他所有点的距离，4号点被更新成dist[4] = 3

• 结束
  得到1号点到5号点的最短距离是5，对应的路径是1 -> 2 -> 4 -> 5，并不是真正的最短距离

那么存在负边权的图怎么求最短距离呢？

时间复杂度 O(nm), n 表示点数，m 表示边数

Bellman - ford 算法是求含负权图的单源最短路径的一种算法，效率较低，代码难度较小。其原理为连续进行松弛，在每次松弛时把每条边都更新一下，若在 n-1 次松弛后还能更新，则说明图中有负环，因此无法得出结果，否则就完成。

bellman - ford算法的具体步骤

for n次
for 所有边 a,b,w (松弛操作)
dist[b] = min(dist[b],dist[a] + w)

int n, m;       // n表示点数，m表示边数
int dist[N];        // dist[x]存储1到x的最短路距离

struct Edge     // 边，a表示出点，b表示入点，w表示边的权重
{
    int a;
    int b;
    int w;
}edges[M];

// 求1到n的最短路距离，如果无法从1走到n，则返回-1。
int bellman_ford()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;

// 如果第n次迭代仍然会松弛三角不等式，就说明存在一条长度是n+1的最短路径，
//由抽屉原理，路径中至少存在两个相同的点，说明图中存在负权回路。
    for (int i = 0; i < n; i ++ )
    {
        for (int j = 0; j < m; j ++ )
        {
            int a = edges[j].a, b = edges[j].b, w = edges[j].w;
                dist[b] = min(dist[b],dist[a] + w)
                
        }
    }

    if (dist[n] > 0x3f3f3f3f / 2) return -1;
    return dist[n];
}

SPFA 算法是 Bellman-Ford算法 的队列优化算法的别称，通常用于求含负权边的单源最短路径，以及判负权环。
SPFA一般情况复杂度是O(m) 最坏情况下复杂度和朴素 Bellman-Ford 相同，为O(nm)。n 表示点数，m 表示边数

算法思想
Bellman_ford算法会遍历所有的边，但是有很多的边遍历了其实没有什么意义，我们只用遍历那些到源点距离变小的点所连接的边即可，只有当一个点的前驱结点更新了，该节点才会得到更新；因此考虑到这一点，我们将创建一个队列每一次加入距离被更新的结点。考虑用BFS来做优化。用一个队列queue，来存放距离变小的节点。

算法步骤
queue <– 1
while queue 不为空
(1) t <– 队头
queue.pop()
(2)用 t 更新所有出边 t –> b，权值为w
queue <– b (若该点被更新过，则拿该点更新其他点)

模板如下：

给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环， 边权可能为负数。
请你求出 1 号点到 n 号点的最短距离，如果无法从 1 号点走到 n 号点，则输出 impossible。
数据保证不存在负权回路。

#include
using namespace std;
const int N=1e5+10;
int h[N],ne[N],e[N],w[N],idx;
int m,n;
queueq;
int st[N],d[N]; //st表示队列里是否有某值; 
 // 存储每个点到1号点的最短距离
 // 存储每个点是否在队列中
void add(int a,int b,int c)
{
    e[idx]=b;w[idx]=c;ne[idx]=h[a],h[a]=idx++;
 } 
int spfa()
{
    d[1]=0;
    q.push(1);
    st[1]=1;                 //表示队列里有1了;         
    while(q.size())
    {
        int t=q.front();q.pop();
        st[t]=0;
        for(int i=h[t];i!=-1;i=ne[i])
        {
            int j=e[i];
            if(d[j]>d[t]+w[i])    //是否可更新; 
            {
                d[j]=d[t]+w[i];   //更新;
                if(!st[j])        //判断队列里是否已经有j; 
                {
                    st[j]=1;      
                    q.push(j);    //没有则将j插入队列; 
                }
            }
        }
    }
    if(d[n]>0x3f3f3f3f/2)cout<<"impossible";   //可能存在负权边; 
    else cout<
    memset(h,-1,sizeof(h));
    memset(d,0x3f,sizeof(d));
    cin>>n>>m;
    for(int i=0;i
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c);
    }
    spfa();
}

若要使用SPFA算法，一定要求图中不能有负权回路。只要图中没有负权回路，都可以用SPFA，这个算法的限制是比较小的。

当然我们也可以用PSFA算法来判断图中有没有负环。

给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环， 边权可能为负数。
如果图中存在负权回路，则输出 Yes，否则输出 No。
请你判断图中是否存在负权回路。

int n;      // 总点数
int h[N], w[N], e[N], ne[N], idx;       // 邻接表存储所有边
int dist[N], cnt[N];        // dist[x]存储1号点到x的最短距离，cnt[x]存储1到x的最短路中经过的点数
bool st[N];     // 存储每个点是否在队列中

// 如果存在负环，则返回true，否则返回false。
bool spfa()
{
    // 不需要初始化dist数组
    // 原理：如果某条最短路径上有n个点（除了自己），那么加上自己之后一共有n+1个点，由抽屉原理一定有两个点相同，所以存在环。

    queue q;
    for (int i = 1; i <= n; i ++ )
    {
        q.push(i);
        st[i] = true;
    }

    while (q.size())
    {
        auto t = q.front();
        q.pop();

        st[t] = false;

        for (int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > dist[t] + w[i])
            {
                dist[j] = dist[t] + w[i];
                cnt[j] = cnt[t] + 1;
                if (cnt[j] >= n) return true;       // 如果从1号点到x的最短路中包含至少n个点（不包括自己），则说明存在环
                if (!st[j])
                {
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }

    return false;
}

莫言真理无穷尽，寸进自有寸进欢