【最短路算法】SPFA-Toy模板网

这篇具有很好参考价值的文章主要介绍了【最短路算法】SPFA。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

引入

在计算机科学的世界里，算法就像是星空中的繁星，各自闪烁着智慧的光芒。它们沉默而坚定，像是一群不语的哲人，默默地解答着世界的问题。

算法的步骤，如同优美的诗行，让复杂的问题在流转的字符中得以释放。它们如同山间清泉，从一座山峰流淌到另一座山峰，涤荡着问题的尘埃，揭示出真实的面貌。

它们像是一把把钥匙，打开了通往计算机科学的大门。我们用它们来解决问题，用它们来创造奇迹。它们是我们智慧的结晶，是我们对世界的理解和对未来的憧憬。

走进这个充满算法的世界，感受那智慧的光芒和诗意的韵律。让我们一起探索未知的领域，寻找那最美的风景和最珍贵的宝藏。

算法不仅是计算机科学的基础，更是我们生活的诗意所在。它们让我们看到了未来的希望，感受到了科技的魅力。所以，让我们一起拥抱算法，让它们为我们的生活增添色彩，为我们的世界带来更多的可能性。

算法就像是计算机科学中的一道道美食佳肴，它们各自拥有独特的味道和风味。有些算法如同细腻的法式甜点，复杂而精致，需要我们耐心地逐一品味；有些算法则如同朴实的乡村面包，简单而实用，让人感到亲切和温暖。

基本介绍

而在这茫茫的算法大海中，有一种算法闪烁着亮丽的光彩——最短路算法。

最短路算法是一种图论算法，用于在加权图中找到两个节点之间的最短路径。这种算法在现实生活中有着广泛的应用，例如：

交通规划：最短路算法可以用于城市交通规划，帮助确定最短路线，以减少交通拥堵和提高交通效率。

物流配送：在物流配送中，最短路算法可以帮助确定最短路径，以最小化运输成本和时间。

网络设计：在计算机网络中，最短路算法可以帮助确定最佳路由，以确保数据包能够以最快的速度传输。

地理信息系统：在地理信息系统中，最短路算法可以用于确定两点之间的最短路径，例如在地图上查找两点之间的最佳路线。

其中，SPFA是打开图论大门的一个钥匙，就让我们走进它吧。

思路

SPFA算法的全称是：Shortest Path Faster Algorithm，是西南交通大学段凡丁于 1994 年发表的论文中的名字。不过，段凡丁的证明是错误的，且在 Bellman-Ford 算法提出后不久（1957 年）已有队列优化内容，所以国际上不承认 SPFA 算法是段凡丁提出的。

为了避免最坏情况的出现，在正权图上应使用效率更高的Dijkstra算法。

若给定的图存在负权边，类似Dijkstra算法等算法便没有了用武之地，SPFA算法便派上用场了。简洁起见，我们约定加权有向图G不存在负权回路，即最短路径一定存在。用数组d记录每个结点的最短路径估计值，而且用邻接表来存储图G。我们采取的方法是动态逼近法：设立一个先进先出的队列用来保存待优化的结点，优化时每次取出队首结点u，并且用u点当前的最短路径估计值对离开u点所指向的结点v进行松弛操作，如果v点的最短路径估计值有所调整，且v点不在当前的队列中，就将v点放入队尾。这样不断从队列中取出结点来进行松弛操作，直至队列空为止。

定理：只要最短路径存在，上述SPFA算法必定能求出最小值。证明：每次将点放入队尾，都是经过松弛操作达到的。换言之，每次的优化将会有某个点v的最短路径估计值d[v]变小。所以算法的执行会使d越来越小。由于我们假定图中不存在负权回路，所以每个结点都有最短路径值。因此，算法不会无限执行下去，随着d值的逐渐变小，直到到达最短路径值时，算法结束，这时的最短路径估计值就是对应结点的最短路径值。

实际上，如果一个点进入队列达到n次，则表明图中存在负环，没有最短路径。

段凡丁论文中的复杂度证明（O(kE)，k 是小常数）是错误的，在此略去。该算法的最坏时间复杂度为 O(VE)。

对SPFA的一个很直观的理解就是由无权图的BFS转化而来。在无权图中，BFS首先到达的顶点所经历的路径一定是最短路(也就是经过的最少顶点数)，所以此时利用数组记录节点访问可以使每个顶点只进队一次，但在带权图中，最先到达的顶点所计算出来的路径不一定是最短路。一个解决方法是放弃数组，此时所需时间自然就是指数级的，所以我们不能放弃数组，而是在处理一个已经在队列中且当前所得的路径比原来更好的顶点时，直接更新最优解。

SPFA算法有四个优化策略：堆优化、栈优化、SLF和LLL。

堆优化：将队列换成堆，与 Dijkstra 的区别是允许一个点多次入堆。在有负权边的图可能被卡成指数级复杂度。

栈优化：将队列换成栈（即将原来的 BFS 过程变成 DFS），在寻找负环时可能具有更高效率，但最坏时间复杂度仍然为指数级。

SLF：Small Label First 策略，设要加入的节点是j，队首元素为i，若dist(j)<dist(i)，则将j插入队首，否则插入队尾；

LLL：Large Label Last 策略，设队首元素为i，队列中所有dist值的平均值为x，若dist(i)>x则将i插入到队尾，查找下一元素，直到找到某一i使得dist(i)<=x，则将i出队进行松弛操作。

SLF 和 LLL 优化在随机数据上表现优秀，但是在正权图上最坏情况为 O(VE)，在负权图上最坏情况为达到指数级复杂度。

归根结底，SPFA就是宽搜，看看就懂了。

#include <bits/stdc++.h>
using namespace std;
struct edge{int x, y, c, pre;} a[410000];int alen, last[11100];
void ins(int x, int y, int c)//ins函数的功能是建立一条从x出发到y且长度为c的边
{
    a[++alen] = edge{x, y, c, last[x]}; 全局增加一条有向边，并赋值
    last[x] = alen;                     //建立边与边的联系（都是从x出发）
}

int n, m, d[11100]; //d[i]表示目前i和出发点的最短距离
bool v[11100];      //v[i]等于true表示点i在更新队列中，等于false表示点i不在更新队列中
void spfa()
{
    memset(d, 63, sizeof(d));d[1] = 0; //初始化d数组，出发点为1，出发点到自己的距离为0
    memset(v, 0, sizeof(v)); v[1] = 1; //初始化v数组，v[1]等于1，表示出发点1进入队列
    deque<int> Q; Q.push_back(1);   //定义更新队列，出发点进入更新队列
    while (!Q.empty()) //只要队列不为空，就表示还有点等着更新别的点
    {
        int x = Q.front();                     //从队列中取出准备好更新别的点的点x
        for (int k = last[x]; k; k = a[k].pre) //重点理解！k首相等于和x相连的最后一条边的编号。那么倒数第二条和x相连的边的编号是多少呢？在a[k].next可以找到
        {
            int y = a[k].y;
            if (d[y] > d[x] + a[k].c) //尝试用x的最短距离更新y的最短距离
            {
                d[y] = d[x] + a[k].c; //如果点被更新了，那么它马上有冲动（想进更新队列）要去更新它的"亲朋好友"（与之直接相连的点）
                if (v[y] == 0)        //如果点y不在队列，则进入队列；如果已经在队列了，则不用再进入。
                {
                    Q.push_back(y);
                    v[y] = 1;
                }
            }
        }
        Q.pop_front(); //此时x已经更新完它的"亲朋好友"，完成使命，退出队列Q
        v[x] = 0;      //标记x已经不再队列，以后x有可能会再次进入队列
    }
    //队列没有点等着更新别的点了，那么意味着所有点的d值都是最优的
    if (d[n] == d[0]) printf("-1\n"); //d[0]为初始的最大值，d[n]等于d[0]表示点n没有被更新，即点n无法到达。
    else              printf("%d", d[n]);
}
int main()
{
    scanf("%d%d", &n, &m);
    alen = 0;
    memset(last, 0, sizeof(last)); //注意构图之前一定要初始化，不然后果很严重！
    for (int i = 1; i <= m; i++)
    {
        int x, y, c;
        scanf("%d%d%d", &x, &y, &c); //题目给出的是无向边，而我们的边目录是有向边
        ins(x, y, c);
        ins(y, x, c); //建立正向边、反向边
    }
    spfa();
    return 0;
}

详细注释都写在代码里面了，好好看。