欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

最短路专题

程序员文章站 2022-06-03 18:36:52
...

 

目录

  绪言  

  Floyd算法O(n^3)

  SPFA算法O(me)



  绪言  

  最短路是图论中的一大经典问题。基本内容是:若网络中的每条边都有一个数值(长度、成本、时间等),则找出两节点(通常是源节点和汇节点)之间总权和最小的路径就是最短路问题。

  通常我们用来求最短路有3种算法——Floyd算法,Dijkstra算法O,Bellman-ford算法的队列优化(SPFA)。

 


  Floyd算法O(n^3)

  对于求多源最短路的题目(需要求出多个点对之间的最短路),我们通常用Floyd算法。虽然复杂度很高,但当我们遇见多源最短路的题时,点的个数通常很少。Floyd算法根据Dp的思想,暴力枚举得出每两个点之间的最短路。

  

for(int k=1;k<=n;k++)//枚举中间点
    for(int i=1;i<=n;i++)//枚举起始点
        for(int j=1;j<=n;j++)//枚举终结点
            if(Dist[i][j]>Dist[i][k]+Dist[k][j])
                 Dist[i][j]=Dist[i][k]+Dist[k][j];

 在Floyd算法中,i和j是可以调换位置的,但是这个k,也就是中间点的枚举,必须要放在外面。Floyd的本质是Dp,i和j表示的是状态,而k表示的则是阶段,作为阶段的值我们通常是要放在循环的最外面的。

 如果要更专业一点,来看一下大神是怎么说的。

 https://www.zhihu.com/question/30955032/answer/50079000

 采用动态规划思想,最短路专题表示最短路专题最短路专题之间可以通过编号为最短路专题的节点的最短路径。
 初值最短路专题为原图的邻接矩阵。

 则最短路专题可以从最短路专题转移来,表示最短路专题最短路专题不经过最短路专题这个节点。
 也可以从最短路专题转移过来,表示经过最短路专题这个点。
 意思即最短路专题

 然后你就会发现最短路专题最外层一维空间可以省略,因为最短路专题只与最短路专题有关

 

  放两道题上来。

  洛谷 P3906 Geodetic集合      

  题解

  [BZOJ] 1491 [洛谷] P2047 [NOI2007] 社交网络

     题解


  SPFA算法O(me)

 关于SPFA,它死了。

 SPFA(Shortest Path Faster Algorithm)基于Bellman-Ford算法(其实就是在此之上加入了队列优化)。在此我们不去讨论SPFA算法到底是谁先提出的以及人们的各种看法。

 单纯考虑算法的话,SPFA能够处理Dijkstra算法无能为力的带有负权的图(甚至可以判断负权环)。

 由于SPFA能够处理的数据范围要比Floyd大,所以用邻接矩阵显然不可取,此时我们要新学习一个很强大的存图方法——邻接表。邻接表

 SPFA算法的大致思想是"动态逼近法",在不断的对点进行松弛操作后得到最短路。而进行松弛的方法和BFS有许多相似之处。但是BFS中每个点只会搜到一次,而SPFA中对同一个点可能进行多次松弛:

 首先建立一个保存待松弛点的队列,将起始点丢进队列中。对于在队列中的每个点Ui,枚举其连出去的边权Wi,边的终点为Vi,如果Dist[Vi]>Dist[Ui]+Wi。此时我们发现我们从Ui走过边Wi到达Vi比之前的走法更优,更新到达Vi的最短路径的值,并且经过Vi到达的点也可能有更优解,也就是说Vi可以再次进行松弛,我们把Vi放入队列的末尾,等待下次松弛(如果Vi已经在队列中就不需要放了)。当起始点到其他每个点的距离都已经达到了最小值时,松弛就会停止。我们以这个图来举个例子。链接

最短路专题

 我们要求出1到其他3个点的最短路。首先初始化路径长度为INF(当然到起始点的长度为0)。

 松弛点1,更新了到2,3,4的路径,将2,3,4丢入队列。此时Dist[1]=0,Dist[2]=2,Dist[3]=5,Dist[4]=4。将1弹出队列。

 松弛点2,更新到3和4的路径,3,4已经在队列中了,不用再次丢进队列。Dist[1]=0,Dist[2]=2,Dist[3]=4,Dist[4]=3。弹出2。

 松弛点3,点3只有到4的边,但是由于当前到4的最短路径已经更新为3了,而Dist[3]+Wi=7>3,所以无法更新。弹出3。

 松弛点4,点4没有出边,无法松弛,弹出4。

 此时队列为空,整张图的松弛结束了,最短路跑完了。

 放出代码

void SPFA(int st)
{
    memset(Dist,INF,sizeof(Dist));
    int head=1,tail=1;
    Dist[st]=0;
    q[head]=st;
    inq[st]=TRUE;
    while(head<=tail)
    {
        int u=q[head++];
        inq[u]=FALSE;
        for(int i=Head[u];i;i=h[i].next)
        {
            int v=h[i].node,w=h[i].w;
            if(Dist[v]>Dist[u]+w)
            {
                Dist[v]=Dist[u]+w;
                if(!inq[v])
                {
                    q[++tail]=v;
                    inq[v]=TRUE;
                }
            }
        }
        
    }
}

 当然SPFA算法有两个民间优化,SLF和LLL

 SLF(Small Label First),设要加入的节点是v,队首元素为u,若Dist[v]<Dist[u],则将v插入队首,否则插入队尾;

 LLL(Large Label Last),设队首元素为u,队列中所有Dist值的平均值为x,若Dist[u]>x则将u插入到队尾,查找下一元素,直到找到某一ui使得Dist[ui]<=x,则将ui出队进行松弛操作。

 SLF 和 LLF 在随机数据上表现优秀,但是在正权图上最坏情况为 O(VE),在负权图上最坏情况为达到指数级复杂度。所以不推荐大家使用,毕竟如果真要卡SPFA的话这两个优化当然也会被卡,其实还可以写个随机进队,虽然也没多大用。

 放出一点题目

 USACO 虫洞&题解

 洛谷P1951 收费站&题解

 USACO GPS的决斗Dueling GPS's&题解

 HNOI2009 最小圈&题解

 

相关标签: 最短路