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。记录几个自己犯的错误:
-
一定注意SPFA中需要使用vis数组来标记当前节点是否已经存在于队列中。否则由于反复加入节点,会爆栈造成MLE。
-
求最短上升距离时,开始的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;
}