SPFA
Shortest Path Faster Algorithm，是一个用于求有向带权图单源最短路径的算法，且适用于带负权的图，能够判断负环。
SPFA的功能还是很强大的，即使有向图存在重边，环，SPFA都可以正确的处理，但是时间复杂度会受影响。
这里的代码是用队列实现的，队列里的结点，是待优化的结点。即该结点指向的所有的结点的最短路径有优化的可能。
图用vector存。vis[i]表示i结点是否在队列中。dist[i]表示源点s到结点i的最短路径。
基于此，算法的基本步骤：
1.初始化dist为inf，vis为0.
1.先把源点s入队，并且做入队标记处理，dist[s]更新为0.
3.从队列中拿出一个结点u，对于结点u指向的所有结点v，判断是否有：dist[v] > dist[u] + w(u->v). 若有，则说明v结点的最短路dist[v]需要优化，同时v指向的结点也有优化的可能，因此更新完v的dist值后，把v入队；若没有，即dist[v]不需要优化，不需要更新，那就不需要处理了。
4.重复步骤3，直至队列为空。输出dist[].
时间复杂度上限O(nm)，点数n，边数m
#include <iostream>
#include <vector>
#include <cmath>
#include <queue>
using namespace std;
const int maxn = 1e4+10,inf = 2147483647;
typedef struct Edge{
int v,w;
}Edge;
int n,m,s;
Edge tmp;
int dist[maxn],vis[maxn];
vector<Edge> G[maxn];
int main(){
int u,v,w;
queue<int> q;
cin >> n >> m >> s;
for (int i=1;i<=m;i++){
cin >> u >> tmp.v >> tmp.w;
G[u].push_back(tmp);
}
for (int i=1;i<=n;i++){
dist[i] = inf;
vis[i] = 0;
}
q.push(s); dist[s] = 0; vis[s] = 1;
while (!q.empty()){
int tmp = q.front(); q.pop();
vis[tmp] = 0;
for (int i=0;i<G[tmp].size();i++){
if (dist[G[tmp][i].v] > dist[tmp]+G[tmp][i].w){
dist[G[tmp][i].v] = dist[tmp]+G[tmp][i].w;
if (!vis[G[tmp][i].v]){
q.push(G[tmp][i].v);
vis[G[tmp][i].v] = 1;
}
}
}
}
for (int i=1;i<=n;i++)
cout << dist[i] << " ";
return 0;
}链式前向星版本
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const int maxn = 1e4+10, maxm = 5e5+5, inf = 2147483647;
typedef struct Edge{
int from,to,weight;
int next;
Edge(){
next = inf;
}
}Edge;
int n,m,s;
int dist[maxn],vis[maxn];
int head[maxn];
int tot;
Edge e[maxm];
void AddEdge(int from,int to,int weight){
tot++;
e[tot].from = from;
e[tot].to = to;
e[tot].weight = weight;
e[tot].next = head[from];
head[from] = tot;
}
int main(){
int from,to,weight;
queue<int> q;
cin >> n >> m >> s;
for (int i=1;i<=m;i++){
cin >> from >> to >> weight;
AddEdge(from,to,weight);
}
for (int i=1;i<=n;i++){
dist[i] = inf;
vis[i] = 0;
}
q.push(s); dist[s] = 0; vis[s] = 1;
while (!q.empty()){
int tmp = q.front(); q.pop();
vis[tmp] = 0;
for (int i=head[tmp];i!=inf;i=e[i].next){
if (dist[e[i].to] > dist[tmp]+e[i].weight){
dist[e[i].to] = dist[tmp]+e[i].weight;
if (!vis[e[i].to]){
q.push(e[i].to);
vis[e[i].to] = 1;
}
}
}
}
for (int i=1;i<=n;i++)
cout << dist[i] << " ";
return 0;
}现在普遍认为SPFA已经死了，但也有很多用到的地方。
说SPFA死了，是因为SPFA是时间复杂度很不稳定的算法，它采取的基本思想就是：源点s到结点i的最短路=min(s到指向i的所有结点j的最短路+w(j->i))
可以想到这样求的话很容易被卡的，，不同的数据即使数据量相同，耗时也可能天差地别！
所以SPFA多用于求负权，判断负环。一般的最短路多用优先权队列优化的Dijkstra算法来求。
SPFA在斯坦纳树中也会用到(因斯坦纳树的数据量很小，用SPFA是很合适的)。
SPFA求负环
SPFA可以处理Dijkstra处理不了的负权图。
负环：一条权值为负数的回路。
那么当一个连通图存在负环时，这个环上的点的最短路是无法求出来的，因为绕着环走一圈，权值会变小，那么最小的话就一直走一直走没有穷尽了。
如何判断负环呢，SPFA算法中，若某个结点被更新了很多很多次，就可以断定它一定处在某个负环内。这个次数的下界是n(点数)。
那么只需要在SPFA的板子上小做修改即可。
时间复杂度是确定的O(nm)
洛谷P3385
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
const int maxn = 2e3+10, maxm = 1e4+5, inf = 2147483647;
typedef struct Edge{
int from,to,weight;
int next;
Edge(){
next = inf;
}
}Edge;
int n,m;
int dist[maxn],vis[maxn],cnt[maxn];
int head[maxn];
int tot;
Edge e[maxm];
inline void AddEdge(int from,int to,int weight){
tot++;
e[tot].from = from;
e[tot].to = to;
e[tot].weight = weight;
e[tot].next = head[from];
head[from] = tot;
}
bool SPFA();
int main(){
int t;
cin >> t;
while (t--){
//memset(head,inf,sizeof head);
//memset(dist,inf,sizeof dist);
for (int i=1;i<maxn;i++)
head[i] = dist[i] = inf;
memset(cnt,0,sizeof cnt);
if (SPFA()) cout << "YES\n";
else cout << "NO\n";
}
return 0;
}
bool SPFA(){
int from,to,weight;
tot = 0;
queue<int> q;
cin >> n >> m;
for (int i=1;i<=m;i++){
cin >> from >> to >> weight;
if (weight>=0){
AddEdge(from,to,weight);
AddEdge(to,from,weight);
}else
AddEdge(from,to,weight);
}
for (int i=1;i<=n;i++){
dist[i] = inf;
vis[i] = 0;
}
q.push(1); dist[1] = 0; vis[1] = 1;
while (!q.empty()){
int tmp = q.front(); q.pop();
vis[tmp] = 0;
for (int i=head[tmp];i!=inf;i=e[i].next){
if (dist[e[i].to] > dist[tmp]+e[i].weight){
dist[e[i].to] = dist[tmp]+e[i].weight;
if (++cnt[e[i].to] >= n)
return 1;
if (!vis[e[i].to]){
q.push(e[i].to);
vis[e[i].to] = 1;
}
}
}
}
return 0;
}小错误：用memset设置值inf时出错了，，，RE
标记最短路径
洛谷P2384 最短路
如何输出最短路上的边呢？？这道题可以用到！
题意看题，因为不断乘的话肯定会爆精度，那么用log操作一下就行了。。但是试了很多次，仍然会有精度的问题，可能是log相加的时候精度不够吧，，最后用了正解：标记最短路径才彻底解决了问题。
标记的方法就是，从1-->n的最短路径中，标记直接到达n的那条边，然后回溯终点即可。
trans[i]表示1->i的最短路中，最后一条边(即直接指向i的那条边)的标号。
#include <cstdio>
#include <cmath>
#include <queue>
using namespace std;
const int maxn = 1e3+5, maxm = 1e6+5, inf = 4153151, mod = 9987;
typedef struct Edge{
int from,to,weight,next;
}Edge;
int n, m, tot;
int head[maxn], vis[maxn], trans[maxn];
double dist[maxn];
Edge e[maxm];
char s[10];
inline void AddEdge(int from, int to, int weight){
tot++;
e[tot].from = from;
e[tot].to = to;
e[tot].weight = weight;
e[tot].next = head[from];
head[from] = tot;
return;
}
int main(){
int u, v, w;
queue<int> q;
scanf ("%d %d",&n, &m);
for (int i=1;i<=n;i++) head[i] = dist[i] = inf;
for (int i=1;i<=m;i++){
scanf ("%d %d %d",&u, &v, &w);
AddEdge(u, v, w);
}
q.push(1); vis[1] = 1; dist[1] = 0;
while (!q.empty()){
int tmp = q.front(); q.pop();
vis[tmp] = 0;
for (int i=head[tmp];i!=inf;i=e[i].next)
if (dist[e[i].to] > dist[tmp] + log2(e[i].weight)){
dist[e[i].to] = dist[tmp] + log2(e[i].weight);
trans[e[i].to] = i;
if (!vis[e[i].to]){
q.push(e[i].to);
vis[e[i].to] = 1;
}
}
}
int tmp = n, ans = 1;
while (tmp!=1){
ans = (ans * e[trans[tmp]].weight) % mod;
tmp = e[trans[tmp]].from;
}
printf ("%d", ans);
return 0;
}
0 条评论