\(Dijkstra\)

前言

当我做另一道题使用最短路算法时，我习惯性地去\(Luogu\)博找\(Dijksttra\)的板子，这时候我觉得这种算法应该记住，于是我又重温了一遍最短路算法，发现了很多困惑，尤其是关于\(SPFA\)和\(Dijkstra\)算法的区别。因为我的\(SPFA\)和\(Dijkstra\)都使用了堆优化。

然后我困惑了很久，终于明白了，准备推样例理解一下，又心血来潮重温了一下\(Dijkstra\)算法为什么不能处理负权边，然后构造了一个带负权的有向图，结果呢。

我的\(Dijkstra\)竟然跑出了正确的答案!

我惊了，拿朋友的板子发现正确的\(Dijkstra\)算法是不能跑负权边的，于是我再去看我的板子，怀疑我的\(Dijkstra\)写成了\(SPFA\)，要是我发现了能处理负权边的\(Dijkstra\)算法，我估计会被保送吧哈哈。于是改掉了我的板子，所幸在\(NOIP\)前发现，在此简单总结一下最短路算法。

\(Floyed\)

多源最短路算法，运用了松弛的思想，有很浓重的\(DP\)气息(因为它就是\(DP\))，通过枚举中间点转移。

复杂度\(O(n^3)\)，在解决最短路问题上基本没有用处，如果解决多源问题完全可以跑\(n\)遍\(Dijkstra\)，和矩阵乘法结合有一些用，具体我也忘了。

memset(f,inf,sizeof(f));for(int i=1;i<=n;++i) f[i][i]=0;for(int i=1;i<=n;++i)    for(int j=1;j<=n;++j)        for(int k=1;k<=n;++k)          f[i][j]=min(f[i][j],f[i][k]+f[k][j]);

\(SPFA\)

\(SPFA\)是个随机数据下比较快的算法，它的思想是每次从队列中找到一个点，松弛它所连的边，然后出队，注意这个点是可以再次被更新的，也就是可以再次入队重新松弛，不断逼近，直到最后求出最优解。所以卡\(SPFA\)的办法就是让\(SPFA\)跑到终点，然后再从起点更新，让它不停地重复跑就可以了，具体方法是构造一个网格图，将横向边边权设为很小，纵边很大即可。

\(SPFA\)最优复杂度为\(O(KE)\)，其中\(K\)是一个常数，但是最坏情况可以达到\(O(VE)\)

众所周知，现在很多最短路题目出题人都会卡\(SPFA\)，用双端队列优化或者是堆优化本质都是不变的，都会被卡，所以还是用\(Dijkstra\)吧。

常规的\(SPFA\)

#include
    
     #define N 10005#define maxn 500005#define INF 2147483647using namespace std;int dis[N],cnt,n,m,eu,ev,head[N],x,y,z,s;bool vis[N];struct Edge{    int next,w,v;}e[maxn];inline void add(int u,int v,int w){    e[++cnt].v=v;    e[cnt].w=w;    e[cnt].next=head[u];    head[u]=cnt;    return;}void spfa(int s){    for(int i=1;i<=n;i++){        dis[i]=INF;        vis[i]=true;    }    dis[s]=0;    queue 
     
       q;    q.push(s);    vis[s]=false;    while(!q.empty()){        eu=q.front();        q.pop();        vis[eu]=true;        for(int i=head[eu];i;i=e[i].next){            ev=e[i].v;            if(dis[eu]+e[i].w
      
       '9'){if(ch=='-')f=-1;ch=getchar();}    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}    return x*f;}int main(){    cin>>n>>m>>s;    for(register int i=1;i<=m;i++)    {        cin>>x>>y>>z;        add(x,y,z);    }    spfa(s);    for(register int i=1;i<=n;i++) printf("%d ",dis[i]);}
      
     
    

比较常用的双端队列优化(\(SLF\)优化)，大概思想是队列为空或者当前最短距离比队首小时放到队首，否则放到队首，最好再熟悉一下\(STL\)

#include
    
     #define N 100005#define maxn 200005#define INF 2147483647using namespace std;int dis[N],cnt,n,m,eu,ev,head[N],x,y,z,s;bool vis[N];struct Edge{    int next,w,v;}e[maxn];inline void add(int u,int v,int w){    e[++cnt].v=v;    e[cnt].w=w;    e[cnt].next=head[u];    head[u]=cnt;    return;}void spfa(int s){    for(int i=1;i<=n;i++){        dis[i]=INF;    }    dis[s]=0;    deque 
     
       q;    q.push_back(s);    vis[s]=1;    while(!q.empty()){        eu=q.front();        q.pop_front();        vis[eu]=0;        for(int i=head[eu];i;i=e[i].next){            ev=e[i].v;            if(dis[eu]+e[i].w
      
        dis[q.back()]) {//                      int fr = q.front() ; q.pop_front() ;//                      int ba = q.back() ; q.pop_back() ;//                      q.push_front(ba), q.push_back(fr) ;//                  }                    if(q.empty()||dis[ev]
       
        '9'){if(ch=='-')f=-1;ch=getchar();}    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}    return x*f;}int main(){    cin>>n>>m>>s;    for(register int i=1;i<=m;i++)    {        x = read(), y = read(), z = read() ;        add(x,y,z);    }    spfa(s);    for(register int i=1;i<=n;i++) printf("%d ",dis[i]);}
       
      
     
    

\(SPFA\)堆优化：算是比较快的，但是不常用，这个可以过掉洛谷的单源最短路（标准版），而且比\(Dijkstra\)要快

#include
    
     #define N 200000 + 10#define maxn 200000 + 10#define INF 2147483647using namespace std;int dis[N],cnt,n,m,eu,ev,head[N],x,y,z,s;bool vis[N];struct Edge{    int next,w,v;}e[maxn];inline void add(int u,int v,int w){    e[++cnt].v=v;    e[cnt].w=w;    e[cnt].next=head[u];    head[u]=cnt;    return;}struct cmp{    bool operator ()(int &x, int &y)    {        return dis[x] > dis[y];    }};void spfa(int s){    for(int i = 1; i <= n; i++) dis[i] = INF;    dis[s]=0;    priority_queue