美文网首页
最短路径 | 优化Bellman-Ford（SPFA）

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

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

    写在前面：

    前面我们谈到了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）:

    1. 对每个要出队的元素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}比较大小。

    2. 如果dis[u]更大，那么将它弹出放到队尾，取队首元素，继续进行重复判断。

    3. 直至存在一个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）

          本文链接：https://www.haomeiwen.com/subject/hjqgzqtx.html

          延伸阅读

          深度阅读

          • 您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

          栏目导航

          热点阅读

          关于我们|服务条款|联系我们|最短路径 | 优化Bellman-Ford（SPFA）|投稿指南|网站地图|RSS订阅|排版工具|手机版

          提供经典美文摘抄,优美散文欣赏,现代诗歌精选,短篇小说,心情随笔,表白情书范文,故事会在线阅读欣赏

          Copyright © 2014-2023 Haomeiwen.com All Rights Reserved. 好美文阅读网 版权所有

          备案信息：桂公网安备 45052102000051号 · 桂ICP备13007215号-3

          本站所收录作品、热点评论等信息部分来源互联网，目的只是为了系统归纳学习和传递资讯

          所有作品版权归原创作者所有，与本站立场无关，如不慎侵犯了你的权益，请联系我们告知，我们将做删除处理！