SPFA算法

· · 个人记录

SPFA是高效的最短路算法中最容易理解的一个（实际上也就是SPFA和Dijkstra俩个）

Bellman-Ford算法详解

嗯嗯来看看吧，虽然SPFA是题目最喜欢卡的算法：

算法介绍：

SPFA实际上是Bellman-Ford的优化，原理跟Bellman-Ford是一样的，即松弛操作（可以点击上面链接回顾，SPFA的主要优点就在于它优化了Bellman-Ford的遍历过程。Bellman-Ford遍历是简单粗暴的，就是考虑最坏情况暴力地循环，但是SPFA在遍历过程中即可以看出什么时候该停止循环，什么时候不该停止循环，这就需要队列来实现。

遍历过程

SPFA遍历过程比较难懂（当然这也是SPFA的精髓所在），下面是其中的过程：

首先建一个队列让元素排队入场。那么第一个入队的是起点（我们将它标记为 A 点）。我们以这个 A 点为中心，对与此点相连的所有点进行松弛操作。只要碰到有过改变的点就让改变了的点拖去排队等待劳改，譬如一开始将 A 相连的 BCD 三点的值从INF改成了一个具体数值，那么这些个被改变的坏小孩（点BCD)就需要被送到队尾然后送去劳改班。在进行了一次松弛操作后，A 点成功从劳改班毕业，出队。然后对于每个在队列里的元素都进行对于与它相连的点的松弛操作，即重复地把队伍里的元素进行劳动改造，同时揪出与这个点相连的那些被改变的点然后再取到队伍后面。只要队列为空即搜索完成。总结一下：

\text{发散松弛相连点，只要改变就入队，松弛完了就出队}

举个栗子：

对于这个图我们首先把 A 入队,第一次松弛改变了 BCD 的值，然后把 A 踢出去。那么很显然，现在

\text{A=0,B=3,C=6,D=18,E=INF} \text{q={B,C,D}}

然后我们让 BCD 入队，首先找 B ，与其相连的点为 AE，很显然 E 肯定会被改变，而 A 现在不需要松弛，因为 A=0，而B+edge_{AB}=3+3=6，或者说本来 B 就是从 A 来的自然不用走回头路。于是我们再把 B 踢出队列，把 E 入队（因为只有它被改变了值）。那么很显然，现在：

\text{A=0 | B=3 | C=6 | D=18 | E=5} \text{q={C,D,E}}

然后讨论现在队头的 C，我们需要讨论的是 CDE，进行松弛计算后，我们发现 E 的值还差1才值得被改变，不管它（其实为了省时间我们最好用 < 而不是 \leq，即当有相等的时候不用再次入队）。接着我们就发现很开心的事情，D 的值可以被改变，但是我们不用把 D 再次放到队尾（注意：如果 E 搜完以后改变了 C，我们自然还会再次搜索 C，而不是理解为搜完E更新后还要再搜 D）所以我们需要一个数组来判断每个点是否存在于队列中，。同理可得，A 被排除。那么很显然，现在：

\text{A=0,B=3,C=6,D=7,E=5} \text{q={D,E}}

同理可得，我们继续遍历接下来的点，接下来的过程就简单了：

1.查找D，啥都没更新，D出队；
2.查找E，更新 D=E+edge[E][D]=5+1=6，其他不更新；
3.查找D，啥都没更新，D出队,队列为空。

最后我们的出了最优解：

\text{A=0,B=3,C=6,D=6,E=5}

代码

栗子举完了就上代码了（简单粗暴）：

#include<bits/stdc++.h>
#define N 1000001
#define INF 0x7fffffff
using namespace std;
bool iqueue[N];//判断是否在队列中 (is_in_queue)
int dis[N];//记录点的值 
struct node
{
    int des,val;
}tmp;//给结构体亿个差评 
vector <node>spfa[N];//给优先队列亿个好评 
queue<int> q;//再给普通队列亿个好评 
int main()
{
    int dotNum,edgeNum,origin;
    scanf("%d%d%d",&dotNum,&edgeNum,&origin);
    for(int i=1;i<=edgeNum;++i)
    {
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        tmp.des=v;tmp.val=w;
        spfa[u].push_back(tmp);
    }
    q.push(origin);
    iqueue[origin]=true;
    for(int i=1;i<=dotNum;++i)
    {
        dis[i]=INF;
    }//初始化点的数据
    dis[origin]=0;
    int u,v,len; 
    while(!q.empty())
    {
        u=q.front();q.pop();
        len=spfa[u].size();
        for(int i=0;i<len;++i)
        {
            v=spfa[u][i].des;
            if(dis[u]+spfa[u][i].val<dis[v])
            {
                dis[v]=dis[u]+spfa[u][i].val;
                if(!iqueue[v])
                {
                    q.push(v);
                    iqueue[v]=true;
                }
            }
        }
        iqueue[u]=false;
    }
    for(int i=1;i<=dotNum;++i)
    {
        if(i==origin)
        {
            cout<<"0 ";
        }
        else
        {
            cout<<dis[i]<<' ';
        }
    }
    return 0;
}

SPFA完成了！！！接下来要打重点的Dijkstra了QAQ。。。

填坑第 \huge{3} 站完成！！！