最短路径 | 优化Bellman-Ford（SPFA）

作者: 0与1的邂逅 | 来源:发表于2019-05-25 21:56 被阅读0次

最短路径 | 优化Bellman-Ford（SPFA）
——Bellman-Ford
算法实现-SPFA
数据结构（十二）：最短路径(Dijkstra算法)
最短路径(Spfa/Dijkstra)
Shortest-Path Algorithms
19-图的最短路径
Aha! Algorithms - Bellman-Ford
数据结构（十三）：最短路径(Floyd算法)
力扣1514——概率最大的路径

写在前面：

前面我们谈到了Bellman-Ford算法，并埋下了一个伏笔。

每进行一次松弛操作，就会有一些顶点已经求得其最短路径，即这些顶点的最短路径的“估计值”变为“确定值”。此后这些顶点的最短路径的值就会一直保持不变，不再受后续松弛操作的影响。但是，每次还是会判断是否需要松弛，这里浪费了时间。

那么，要怎么优化呢？如何知道当前哪些点的最短路径发生了变化？

我们可以用一个队列来维护这些点。

队列优化Bellman-Ford

算法流程：

图解：

参考代码：【 (数组实现)邻接表构图】

PS：数组实现邻接表可能较难理解，可以看一下这里

这里用一个book数组来记录每个顶点是否在队列中。其实也可以不用book数组，检查一个顶点是否在队列中，只需要遍历一遍整个队列就可以了，但是那样时间复杂度就相对比较高，达到 $O(N)$ ，而使用book数组来记录，时间复杂度将降为 $O(1)$ 。

#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;

const int VexNum=1e3+1;// 顶点数 
const int ArcNum=6e6;// 边数 
const int INF=0x3f3f3f3f;// 正无穷 
// first数组大小要比 n大 1，next数组大小要比 m大 1 
int first[VexNum],next[ArcNum];
// u、v、w数组大小要比 m大1 
int u[ArcNum],v[ArcNum],w[ArcNum];
int dis[VexNum];// 距离表 
int book[VexNum];// 记录哪些顶点已经在队列中 
int n,m;// n：顶点；m：边 

int main()
{
    scanf("%d%d",&n,&m);
    
    // 初始化dis数组 
    for(int i=1;i<=n;i++)dis[i]=INF;
    dis[1]=0;
    
    // 初始化book数组，0表示顶点不在队列中 
    for(int i=1;i<=n;i++)book[i]=0;
    
    // 初始化first数组，-1表示暂时没有边 
    for(int i=1;i<=n;i++)first[i]=-1;
    
    // 读入每条边 
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&u[i],&v[i],&w[i]);
        // 建立邻接表的关键
        next[i]=first[u[i]];
        first[u[i]]=i; 
    }
    
    queue<int>q;// 创建队列 
    q.push(1);// 1号顶点入队 
    book[1]=1;// 1号顶点已在队列中
    
    // 当队列不为空 
    while(!q.empty())
    {
        int k=q.front();// 取队首元素 
        // 队首元素出队列 
        q.pop();
        book[k]=0;// 出队列 
        // 扫描当前顶点所有的边 
        while(k!=-1)
        {
            // 判断是否松弛成功 
            if(dis[v[k]]>dis[u[k]]+w[k])
            {
                dis[v[k]]=dis[u[k]]+w[k];
                // 用book数组来判断顶点v[k]是否在队列中 
                if(book[v[k]]==0)
                {
                    q.push(v[k]);
                    book[v[k]]=1;// 入队列 
                }
            }
            k=next[k];
        }
    }
    for(int i=1;i<=n;i++)
    {
        printf("%d ",dis[i]);
    }
    printf("\n"); 
    return 0;
}

时间复杂度：

该算法的复杂度为 $O(k|M|)$ ，其中 $M$ 为边数， $k$ 是个比较小的常数。不过其证明好像是错误的。(参见百度百科)

最坏情况的时间复杂度也是 $O(NM)$ 。

SPFA算法

最短路径快速算法（英语：Shortest Path Faster Algorithm (SPFA)），国际上一般认为是队列优化的贝尔曼-福特算法，是一个用于求解有向带权图单源最短路径的算法。这一算法被认为在随机的稀疏图上表现出色，并且适用于带有负边权的图。^[1] 然而SPFA在最坏情况的时间复杂度与贝尔曼-福特算法相同，因此在非负边权的图中仍然最好使用戴克斯特拉算法。^[2] SPFA算法首先在1959年由Edward F. Moore作为广度优先搜索的扩展发表^[3]。相同算法在1994年由段凡丁重新发现。^[4]
——《维基百科》

优化技巧：

SPFA算法的性能很大程度上取决于用于松弛其他节点的备选节点的顺序。

事实上，如果 $Q$ 是一个优先队列，则这个算法将极其类似于戴克斯特拉算法。然而尽管这一算法中并没有用到优先队列，仍有两种可用的技巧可以用来提升队列的质量，并且借此能够提高平均性能（但仍无法提高最坏情况下的性能）。

两种技巧通过重新调整 $Q$ 中元素的顺序从而使得更靠近源点的节点能够被更早地处理。因此一旦实现了这两种技巧， $Q$ 将不再是一个先进先出队列，而更像一个链表或双端队列。

（想想也是，如果我们能够在一开始查找的时候，将可能是更短的路径找到，那么，最终找最短路径花的时间也就可能更少。）

——《维基百科》

距离小者优先 SLF（Small Label First）:
原队列改为双向队列，对一个要加入队列的点u，如果 $dis[u]$ 小于队首元素v的 $dis[v]$ ，那么就加入到队首，否则加入到队尾。

//【SLF】 
// 原队列改为双端队列，对一个要加入队列的点u，
// 如果dis[u] 小于队首元素v的dis[v]，那么就加入到队首元素，
// 否则加入到队尾。
#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;

const int VexNum=1e3+1;// 顶点数 
const int ArcNum=6e6;// 边数 
const int INF=0x3f3f3f3f;// 正无穷 
// first数组大小要比 n大 1，next数组大小要比 m大 1 
int first[VexNum],next[ArcNum];
// u、v、w数组大小要比 m大1 
int u[ArcNum],v[ArcNum],w[ArcNum];
int dis[VexNum];// 距离表 
int book[VexNum];// 记录哪些顶点已经在队列中 
int n,m;// n：顶点；m：边 

int main()
{
    scanf("%d%d",&n,&m);
    // 初始化dis数组 
    for(int i=1;i<=n;i++)dis[i]=INF;
    dis[1]=0;
    
    // 初始化book数组，0表示顶点不在队列中 
    for(int i=1;i<=n;i++)book[i]=0;
    
    // 初始化first数组，-1表示暂时没有边 
    for(int i=1;i<=n;i++)first[i]=-1;
    
    // 读入每条边 
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&u[i],&v[i],&w[i]);
        // 建立邻接表的关键
        next[i]=first[u[i]];
        first[u[i]]=i; 
    }
    
    deque<int>dq;// 创建双向队列deque
    dq.push_back(1);// 1号顶点入队尾 
    book[1]=1;// 1号顶点已在队列中
    
    // 当队列不为空 
    while(!dq.empty())
    {
        int k=dq.front();// 取队首元素 
        int temp=k;
        // 队首元素出队列 
        dq.pop_front();
        book[k]=0;
        // 扫描当前顶点所有的边 
        while(k!=-1)
        {
            // 判断是否松弛成功 
            if(dis[v[k]]>dis[u[k]]+w[k])
            {
                dis[v[k]]=dis[u[k]]+w[k];
                // 用book数组来判断顶点v[k]是否在队列中 
                if(book[v[k]]==0)
                {
                    if(dis[temp]>dis[v[k]])dq.push_front(v[k]);// 入队首
                    else dq.push_back(v[k]);// 入队尾
                    book[v[k]]=1;
                }
            }
            k=next[k];
        }
    }
    for(int i=1;i<=n;i++)
    {
        printf("%d ",dis[i]);
    }
    printf("\n"); 
    return 0;
}

距离大者置后 LLL（Large Label Last）:

对每个要出队的元素u，比较 $dis[u]$ 和队列中每个元素
dis的平均值。即： $dis[u] 与 \frac{\sum_{i=0}^{len-1}dis[j]_{j∈Q}}{len}$ 比较大小，也就是 $dis[u]*len$ 与 $\sum_{i=0}^{len-1}dis[j]_{j∈Q}$ 比较大小。
如果 $dis[u]$ 更大，那么将它弹出放到队尾，取队首元素，继续进行重复判断。
直至存在一个 $dis[x]$ 小于平均值，将元素 $x$ 出队。

//【LLL】 
// 对每个要出对的元素u，比较dis[u]和队列中dis的平均值， 
// 如果dis[u]更大，那么将它弹出放到队尾，取队首元素在进行重复判断，
// 直至存在dis[x]小于平均值 
#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;

const int VexNum=1e3+1;// 顶点数 
const int ArcNum=6e6;// 边数 
const int INF=0x3f3f3f3f;// 正无穷 
// first数组大小要比 n大 1，next数组大小要比 m大 1 
int first[VexNum],next[ArcNum];
// u、v、w数组大小要比 m大1 
int u[ArcNum],v[ArcNum],w[ArcNum];
int dis[VexNum];// 距离表 
int book[VexNum];// 记录哪些顶点已经在队列中 
int n,m;// n：顶点；m：边 

long long sum=0;
int len=1;

int main()
{
    scanf("%d%d",&n,&m);
    
    // 初始化dis数组 
    for(int i=1;i<=n;i++)dis[i]=INF;
    dis[1]=0;
    
    // 初始化book数组，0表示顶点不在队列中 
    for(int i=1;i<=n;i++)book[i]=0;
    
    // 初始化first数组，-1表示暂时没有边 
    for(int i=1;i<=n;i++)first[i]=-1;
    
    // 读入每条边 
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&u[i],&v[i],&w[i]);
        // 建立邻接表的关键
        next[i]=first[u[i]];
        first[u[i]]=i; 
    }
    
    queue<int>q;// 普通队列
    q.push(1);// 1号顶点入队 
    book[1]=1;// 1号顶点已在队列中
    len=1;// 对内元素个数 
    sum=0;// 对内元素总和 
    
    // 当队列不为空 
    while(!q.empty())
    {
        int k=q.front();// 取队首元素 
        while(dis[k]*len>sum)
        {
            q.pop();
            q.push(k);
            k=q.front();
        }
        q.pop();
        len--;// 出队，队内元素数-1 
        sum-=dis[k];// 出队，队内元素总和减去出队的元素 
        book[k]=0;
    
        // 扫描当前顶点所有的边 
        while(k!=-1)
        {
            // 判断是否松弛成功 
            if(dis[v[k]]>dis[u[k]]+w[k])
            {
                dis[v[k]]=dis[u[k]]+w[k];
                // 用book数组来判断顶点v[k]是否在队列中 
                if(book[v[k]]==0)
                {
                    q.push(v[k]);
                    sum+=dis[v[k]];
                    len++;
                }
            }
            k=next[k];
        }
    }
    for(int i=1;i<=n;i++)
    {
        printf("%d ",dis[i]);
    }
    printf("\n"); 
    return 0;
}

SLF+LLL：
将前面两种优化方法结合起来，即可。

#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;

const int VexNum=1e3+1;// 顶点数 
const int ArcNum=6e6;// 边数 
const int INF=0x3f3f3f3f;// 正无穷 
// first数组大小要比 n大 1，next数组大小要比 m大 1 
int first[VexNum],next[ArcNum];
// u、v、w数组大小要比 m大1 
int u[ArcNum],v[ArcNum],w[ArcNum];
int dis[VexNum];// 距离表 
int book[VexNum];// 记录哪些顶点已经在队列中 
int n,m;// n：顶点；m：边 
long long sum=0;
int len=1; 

int main()
{
    scanf("%d%d",&n,&m);
    
    // 初始化dis数组 
    for(int i=1;i<=n;i++)dis[i]=INF;
    dis[1]=0;
    
    // 初始化book数组，0表示顶点不在队列中 
    for(int i=1;i<=n;i++)book[i]=0;
    
    // 初始化first数组，-1表示暂时没有边 
    for(int i=1;i<=n;i++)first[i]=-1;
    
    // 读入每条边 
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&u[i],&v[i],&w[i]);
        // 建立邻接表的关键
        next[i]=first[u[i]];
        first[u[i]]=i; 
    }
     
    deque<int>dq;// 双向队列 
    dq.push_back(1);// 1号顶点入队尾 
    book[1]=1;// 1号顶点已在队列中
    sum=0;
    len=1;
    
    // 当队列不为空 
    while(!dq.empty())
    {
        int k=dq.front();// 取队首元素 
        while(dis[k]*len>sum)
        {
            dq.pop_front();// 出队首元素
            dq.push_back(k);// 将其压入队尾 
            k=dq.front();// 取队首元素 
        }
        int temp=k;
        // 队首元素出队列 
        dq.pop_front();
        len--;
        sum-=dis[k];
        book[k]=0;
        // 扫描当前顶点所有的边 
        while(k!=-1)
        {
            // 判断是否松弛成功 
            if(dis[v[k]]>dis[u[k]]+w[k])
            {
                dis[v[k]]=dis[u[k]]+w[k];
                // 用book数组来判断顶点v[k]是否在队列中 
                if(book[v[k]]==0)
                {
                    if(dis[temp]>dis[v[k]])dq.push_front(v[k]);
                    else dq.push_back(v[k]);
                    book[v[k]]=1;// 入队列 
                }
            }
            k=next[k];
        }
    }
    for(int i=1;i<=n;i++)
    {
        printf("%d ",dis[i]);
    }
    printf("\n"); 
    return 0;
}

写在最后：

参考资料：

在学习的过程中，不断总结，虽花时间，但也不无收获。

水平有限，如有错误或建议，还望指出！！！

最短路径 | 优化Bellman-Ford（SPFA）
写在前面：前面我们谈到了Bellman-Ford算法，并埋下了一个伏笔。每进行一次松弛操作，就会有一些顶点已经...
——Bellman-Ford
初始状态：模板：1 模板2:FIFO队列优化 Spfa是Bellman-Ford算法利用队列的优化，Bellma...
算法实现-SPFA
参考:最短路径问题---SPFA算法详解
数据结构（十二）：最短路径(Dijkstra算法)
通过上一章最短路径(Bellman-Ford算法)的内容可知，Bellman-Ford 算法是通过重复对边集执行松...
最短路径(Spfa/Dijkstra)
单源最短路问题(SSSP)常用的算法有Dijkstra，Bellman-Ford，这两个算法进行优化，就有了Dij...
Shortest-Path Algorithms
Bellman-Ford Problem: 求取单源最短路径，可判断有无负环 Complexity: O(VE) ...
19-图的最短路径
图的最短路径迪杰斯特拉算法贝尔曼-福特算法弗洛伊德算法 SPFA算法(中国西南交通大学段凡丁发明) 最短路径...
Aha! Algorithms - Bellman-Ford
《啊哈！算法》第 6 章第 3 节，Bellman-Ford 算法求最短路径的 Swift 实现。问题已知 5...
数据结构（十三）：最短路径(Floyd算法)
Bellman-Ford 算法或者 Dijkstra 算法用于解决单源最短路径问题，获取从指定起点出发，到达图中各...
力扣1514——概率最大的路径
本题主要和图的遍历求解最短路径相关，可以用 Dijkstra 或者 Bellman-Ford 算法进行解决。原题...