算法笔记.spfa算法(bellman-ford算法的改进)

题目：（来源于AcWing）

给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环， 边权可能为负数。

请你求出 1 号点到 n 号点的最短距离，如果无法从 1 号点走到 n 号点，则输出 impossible。

数据保证不存在负权回路。

输入格式

第一行包含整数 n 和 m。

接下来 m 行每行包含三个整数 x,y,z，表示存在一条从点 x 到点 y 的有向边，边长为 z。

输出格式

输出一个整数，表示 1 号点到 n 号点的最短距离。

如果路径不存在，则输出 impossible。

数据范围

1≤n,m≤105,
图中涉及边长绝对值均不超过 10000。

输入样例：

3 3
1 2 5
2 3 -3
1 3 4

输出样例：

2

改进思路：

我们发现，只有一个节点的最短路径被更新之后，这个节点才可能被用来继续更新其出边的节点的最短路径。

代码实现：

 

#include<iostream>
#include<algorithm>
using namespace std;
#include<queue>
int n,m;
const int N = 100010;
int h[N],e[N],ne[N],w[N],idx;
int dist[N];
bool exi[N];//存储队列中是否已经有这个点了void add(int a,int b,int c)
{e[idx] = b;ne[idx] = h[a];w[idx] = c;h[a] = idx++;
}int spfa()
{queue<int> q;q.push(1);dist[1] = 0;exi[1] = true;while(q.size()){int nownode = q.front();q.pop();exi[nownode] = false;//取出该节点后更新exi数组//遍历出边for(int i = h[nownode];i!=-1;i=ne[i]){int tempnode = e[i];if(dist[tempnode] > dist[nownode]+w[i]){dist[tempnode] = dist[nownode]+w[i];if(!exi[tempnode]){q.push(tempnode);//只有本节点最短路被更新了，才需要更新这个节点的出边exi[tempnode] =true;}}}}if(dist[n] ==0x3f3f3f3f) return 0x3f3f3f3f;return dist[n];
}int main()
{fill(h,h+N,-1);//必须在存储边操作前初始化fill(dist,dist+N,0x3f3f3f3f);idx = 0;scanf("%d%d",&n,&m);while(m--){int a,b,c;scanf("%d%d%d",&a,&b,&c);add(a,b,c);}int t = spfa();if(t == 0x3f3f3f3f)cout <<"impossible"<<endl;else cout << t<<endl;return 0;
}

细节：

1.  需要记录队列中是否已经存在该节点，如果已经存在，即便其被更新，也不用再添加它。

2. 头指针h[]要在添加边之前初始化为-1.

spfa算法判断负环：

只需要添加数组count[]，记录每个节点最短路径，上的边的数量，如果边数>n，说明存在负环。

spfa算法的性能： 

1. 时间复杂度可以为O(n+m），但最坏时退化为O(nm）。
2. 可以处理自环、重边、负环、允许边权为负。