SPFA算法
本质是对Bellman-Ford算法的一个优化
利用宽搜做优化
queue<-起点1入队
while queue 不空
取出队头(t<-q.front);q.pop();
更新一下t的所有出边;
queue<-b;
算法1
算法思路不难,y总都是直接用Dijkstra最短路改的,本质也就是用了队列优化for loop。
在此直接记录一下关于sfpa函数的思路,其余的也就是模板,背一背即可。
1.初始化dist数组(十分重要,虽然就两个语句),随后进行队列的初始化,将队头也就是1插入队列,更新state数组为ture也就是已被使用。
2.for loop一遍即可,但是关键就在这一步,用j字母存放当前边,比较通过当前边的距离和通过t这个点的距离哪个小,更新到j的dist数组中,随后检查是否被使用,若没有,加入队列。
关键语句解读
理解这个语句之前,要知道一些东西,比如h是指头结点,ne指的next数组也就是头结点的下一个节点,e指的是存放该边数字的数组,w存的权值大小。
for(int i= h[t];i!=-1;i=ne[i])
{
int j=e[i];
if(dist[j]>dist[t]+w[i])
{
dist[j]=dist[t]+w[i];
if(!st[j])
{
q.push(j);
st[j]=true;
}
}
}
首先,把h的值取出来,在e中找到h真正是第几号结点。
在进行下一步时,我们要明确t是指向的队头结点,i指向的是链队头结点。
随后,进行比较,这个比较是指从t也就是1直接到j的路径和1通过i到j的路径的大小
更新,判断是否需要插入,不需要则进行下一步。
样例详细图解如下:
总体模拟的就是从1开始往后走往后找路径的过程,若有更近的则进行更新,需要注意的是idx默认由0开始,最开始插入的链为0。
为什么是dist[j]=dist[t]+w[i]?
因为t代表的是从初始结点往后延伸的路径,t是指与初始结点直接相连的点的路径,w是指走该路径的代价需要往回找,比如1->2的代价存在w[0]里面,以此类推。
C++ 代码
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
const int N=1e5+10;
int n,m;
int h[N],e[N],ne[N],w[N],idx;
int dist[N];
bool st[N];
void add(int a,int b,int c)//把以c为权值的b插入a链
{
e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}
int sfpa()
{
memset(dist,0x3f,sizeof dist);dist[1]=0;
queue<int> q;
q.push(1);
st[1]=true;
while(q.size())
{
int t=q.front();
q.pop();
st[t]=false;
for(int i= h[t];i!=-1;i=ne[i])
{
int j=e[i];
if(dist[j]>dist[t]+w[i])
{
dist[j]=dist[t]+w[i];
if(!st[j])
{
q.push(j);
st[j]=true;
}
}
}
}
if(dist[n]>0x3f3f3f3f/2) return -1;
return dist[n];
}
int main()
{
scanf("%d%d",&n,&m);
memset(h,-1,sizeof h);
while(m--)
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
add(a,b,c);
}
int t=sfpa();
if(t==-1)puts("impossible");
else cout<<t<<endl;
return 0;
}