最短路专题

 

目录

　　绪言　　

　　Floyd算法O(n^3)

　　SPFA算法O(me)

---

---

　　绪言　　

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

　　通常我们用来求最短路有３种算法——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 最小圈&题解