SPFA/Ford

简单的开始~

Posted by Lin_Xuan on January 11, 2021

SPFA

SPFA的原称呼是Shortest Path Faster Algorithm,也算是单源最短路的一个经典算法……但是由于有很多特殊数据会卡掉它,所以还是使用堆优化的dijskral更为保险。但是,有负权边存在时,difskral算法就不能用了。而SPFA仍然具有较好的复杂度。

算法思路:

首先要维护一个队列que和源点到其他点当前的最短距离dis[i]。取队列头部的点i,遍历i的所有边。如果某条边(i,j)可以更新``dis[j](满足$dis[i]+weight(i,j)<dis[j]$),那么更新最短距离dis[j],**同时判断节点j是否已经在队列里了**,如果不在队列中,则将节点j`放入队列。重复这个过程直到队列为空。

为了防止题目中出现负环,我们可以维护每个点进入队列的次数num[i]。如果这个数值大于点的总数n,哪么说明存在负权环,该图无解。

SPFA的复杂度为$O(e\times k)$,k为每个顶点进入队列的次数。一般情况下,k<2,但是在特殊构造过的图里,k会变得很大。(存在负权环的图中甚至会死循环)

该算法是思路与BFS相似。但是BFS访问过的节点不能被再次访问,而SPFA允许重复访问节点,因此即使存在负权边,也可以成功更新所有的节点。

模板代码

使用vector实现的邻接表存图

bool SPFA(int n,int m,int st,vector<vector<pair<int,int>> >&edg,vector<int>& dis)
{    //点数,边数,起始点,邻接表存边,距离的参数

    
	vector<int> num(n+1);
    vector<bool> vis(n+1);
    for(int i=1;i<=m;i++){
        int u,v,w;
        cin>>u>>v>>w;
        edg[u].push_back(pair(v,w));
        // edg[v].push_back(u);//无向图
    }
    queue<int> que;
    que.push(st);
    fill(dis.begin(),dis.end(),inf);
    dis[st]=0;
    vis[st]=true;
    while (!que.empty())
    {
        int u=que.front();
        vis[u]=false;
        que.pop();
        num[u]++;
        if(num[u]>=n) return false;//存在环
        for(auto e:edg[u])
            if(dis[u]+e.second<dis[e.first])
            {
                dis[e.first]=dis[u]+e.second;
                if(vis[e.first]==false){
                    que.push(e.first);
                    vis[e.first]=true;
                }
            }
    }
    return true;//没有负权环
}

题目练习

Zoj 3088

题目链接

题目大意:

在滑雪场,有n条滑道,m个电梯。一次路径为:从一个点出发,乘坐电梯到达一个点,然后使用滑道回到出发点。求一次路径上滑道上距离与电梯上距离的最大值,同时输出路径。

解题思路:

这题需要求任意两点之间的最短上升和最长下降距离。n为1000,Floyd肯定不行。因此需要求n次SPFA。由于SPFA的玄学复杂度$O(kn)$,总复杂度为$O(kn^2)$,k一般不超过2,所以是可行的。

同时,将下降的路径反向储存,这样只需同时堆节点i求上升和下降的SPFA即可得到从节点i出发的所有上升和下降路径长度。由于需要保存路径,选择SPFA过程中保存当前节点的更新信息(从几号节点更新而来的)。每求完一个点就去更新答案。

但是由于两张图分别求最长路和最短路,同时还要求输出路径,代码变得极其恶心,中间很容易出bug。记录几个自己犯的错误:

  1. 一定注意SPFA中需要使用vis数组来标记当前节点是否已经存在于队列中。否则由于反复加入节点,会爆栈造成MLE。

  2. 求最短上升距离时,开始的dis_lift数组被初始化为inf,因此在求完SPFA后更新最大ans时,需要判断作为除数的dis_lift[j]不为inf(不用判断是否为0,从inf开始更新的点除了源点不可能为0)。否则尽管dis_ski[j]/dis_lift[j]是一个极小值,仍然可以使得ans更新,错误条件下获取路径引发RE问题。

代码:
#ifndef _USE_MATH_DEFINES

#define _USE_MATH_DEFINES

#endif

// #include<bits/stdc++.h>
#include <iostream>

#include <functional>

#include<vector>

#include<queue>

#include<algorithm>

#include<iomanip>

#include<iso646.h>

using namespace std;
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

#define  m_p make_pair

#define   P  pair<int,int>

#define x first

#define y second 

typedef long long LL;
typedef unsigned long long ULL;
typedef long double LD;
const int inf=0x3f3f3f3f;

int main()
{
    IOS;
    #ifdef _DEBUG

    freopen("D:/CODE/algorithm_contest/out.txt","w",stdout);
    freopen("D:/CODE/algorithm_contest/in.txt","r",stdin);  
    #elif _LINUX

    freopen("/media/linxuan/储存/CODE/algorithm_contest/out.txt","w",stdout);
    freopen("/media/linxuan/储存/CODE/algorithm_contest/out.txt","r",stdin);
    #endif
    

    int n,m,k;
    int t; cin>>t;
    while(t--)
    {
        cin>>n>>m>>k;
        vector<vector<P>> edg_lift(n+1),edg_ski(n+1);
        for(int i=1;i<=m;i++){
            int u,v,w;
            cin>>u>>v>>w;
            edg_ski[v].push_back(P(u,w));//为了之后好操作,反向存边
        }
        for(int i=1;i<=k;i++){
            int u,v,w;
            cin>>u>>v>>w;
            edg_lift[u].push_back(P(v,w));
        }
        // 默认不存在环
        vector<int> dis_lift(n+1),dis_ski(n+1);
        vector<int> front_lift(n+1),front_ski(n+1);//记录路径,每个节点的上一个点
        vector<bool> vis_lift(n+1),vis_ski(n+1);//标记这个值是否已经在队列里面
        function<void(int)> SPFA_lift=[&](int st)->void
        {
            //求电梯距离的最小值;
            fill(dis_lift.begin(),dis_lift.end(),inf);
            fill(front_lift.begin(),front_lift.end(),-1);
            fill(vis_lift.begin(),vis_lift.end(),0);
            dis_lift[st]=0;
            vis_lift[st]=true;
            queue<int> que;
            que.push(st);
            while(!que.empty())
            {
                st=que.front();
                vis_lift[st]=false;
                que.pop();
                for(auto &e:edg_lift[st])
                    if(dis_lift[st]+e.y<dis_lift[e.x])
                    {
                        front_lift[e.x]=st;
                        dis_lift[e.x]=dis_lift[st]+e.y;
                        if(vis_lift[e.x]==false){
                            que.push(e.x);
                            vis_lift[e.x]=true;
                        }
                    }
            }
        };
        function<void(int)> SPFA_ski=[&](int st)->void
        {
            //求滑雪距离的最大值;
            fill(dis_ski.begin(),dis_ski.end(),0);
            fill(front_ski.begin(),front_ski.end(),-1);
            fill(vis_ski.begin(),vis_ski.end(),0);
            queue<int> que;
            que.push(st);
            vis_ski[st]=true;
            while(!que.empty())
            {
                st=que.front();
                vis_ski[st]=false;
                que.pop();
                for(auto &e:edg_ski[st])
                    if(dis_ski[st]+e.y>dis_ski[e.x])
                    {
                        front_ski[e.x]=st;
                        dis_ski[e.x]=dis_ski[st]+e.y;
                        if(vis_ski[e.x]==false){
                            que.push(e.x);
                            vis_ski[e.x]=true;
                        }

                    }
            }
        };

        double ans=0;
        vector<int> path;
        for(int i=1;i<=n;i++)//从i出发
        {
            if(edg_lift[i].empty() or edg_ski[i].empty()) continue;//剪枝
            SPFA_lift(i);
            SPFA_ski(i);
            for(int j=1;j<=n;j++)//到达j点
            {
                if(i==j or dis_lift[j]==inf) continue;
                if(1.0*dis_ski[j]/dis_lift[j]>ans)//更新答案
                {
                    ans=1.0*dis_ski[j]/dis_lift[j];
                    // 储存路径
                    int st=j;
                    vector<int>().swap(path);
                    while(st!=i){
                        path.push_back(st);
                        st=front_lift[st];
                    }
                    path.push_back(i);
                    reverse(path.begin(),path.end());
                    path.pop_back();//去掉多余的一个中间节点
                    st=j;
                    while(st!=i){
                        path.push_back(st);
                        st=front_ski[st];
                    }
                    path.push_back(i);
                }
            }
        }
        for(auto i:path) cout<<i<<" ";
        cout<<endl<<fixed<<setprecision(3)<<ans<<endl;
        //清理掉vector占用的内存,可以去掉
        vector<int>().swap(dis_lift);
        vector<int>().swap(dis_ski);
        vector<int>().swap(front_lift);
        vector<int>().swap(front_lift);
        vector<vector<P>>().swap(edg_lift);
        vector<vector<P>>().swap(edg_ski);
        vector<bool>().swap(vis_lift);
        vector<bool>().swap(vis_ski);
    }
    return 0;
}