Bellman-Ford算法的改进---SPFA算法

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

传送门：

Dijkstra

Bellman-Ford

SPFA

Floyd

1.算法思想

Bellman-Ford算法时间复杂度比较高，在于Bellman-Ford需要递推n次，每次递推需要扫描所有的边，在递推n次的过程中，很多判断是多余的，所以考虑用队列优化，减少不必要的判断，这种算法称为SPFA（Shortest Path Faster Algorithm）

SPFA算法的大致流程就是用一个队列来进行维护，初始时将源点加入队列，每次从队列中取出一个顶点，并对它所有相邻的节点进行松弛，如果某个顶点松弛成功，则将其入队，重复这样的过程，直至队列为空为止。时间复杂度在O(Km)(通常K为2左右)一个顶点可以多次入队，但是如果有顶点入队次数大于n次，那就存在负环，此时应当返回存在负环信息

2.算法过程

在SPFA算法中同样可以用dist数组表示最短路长度，path数组保存路径，还需要设置cnt数组记录入队次数，vis数组记录当前是否在队列中

（1）.取出队列头结点u，扫描从顶点u出发的每条边，设每条边的终点为v，边的权值为w（u, v）。如果dist[u] + w < dist[v],则将dist[v]修改成dist[u] + w<u, v>。修改path[v] = u，如果顶点v不在队列中，还需要将v加入队列并且入队次数加一。如果上述条件不成立就不做任何处理

（2）.重复1直至队列为空或者某个顶点入队次数大于n

3.算法实现

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<sstream>
using namespace std;
typedef long long ll;
const int maxn = + ;
const int INF = << ;
int T, n, m, cases;
struct Edge
{
int u, v, w;
Edge(){}
Edge(int u, int v, int w):u(u), v(v), w(w){}
};
vector<Edge>edges;//把每一条边存下来
vector<int>Map[maxn];//G[i]这个vector存的是以i为起点的所有边在edges里面的下标
void init(int n)
{
for(int i = ; i <= n; i++)Map[i].clear();
edges.clear();
}
void addedge(int u, int v, int w)
{
edges.push_back(Edge(u, v, w));//注意无向图需要存两条边
m = edges.size();
Map[u].push_back(m - );
}
void Find(int u)//遍历以u为起点的所有边
{
for(int i = ; i < Map[u].size(); i++)
{
Edge&e = edges[Map[u][i]];
//使用e就可以遍历以u为起点的所有的边
}
}
int cnt[maxn];
bool vis[maxn];
int d[maxn], path[maxn];
bool SPFA(int u)
{
queue<int>q;
memset(vis, , sizeof(vis));//初始化
memset(cnt, , sizeof(cnt));
memset(path, -, sizeof(path));
for(int i = ; i < n; i++)d[i] = INF;
d[u] = ;
vis[u] = ;//标记进入队列
q.push(u);
while(!q.empty())
{
int u = q.front();
q.pop();
vis[u] = ;//清除进入队列标记
for(int i = ; i < Map[u].size(); i++)
{
Edge& e = edges[Map[u][i]];
if(d[u] < INF && d[e.v] > d[u] + e.w)
{
d[e.v] = d[u] + e.w;
path[e.v] = Map[u][i];//path存的是边的下标,这样可以通过边找出之前的点以及每条路的路径，如果用邻接矩阵存储的话这里可以直接存节点u
if(!vis[e.v])
{
q.push(e.v);
vis[e.v] = ;
if(++cnt[e.v] > n)return true;//进队次数大于n，说明存在负环
}
}
}
}
for(int i = ; i < n; i++)
{
if(i == u)continue;
printf("从%d到%d距离是：%2d ", u, i, d[i]);
stack<int>q;//存的是边的编号
int x = i;//x就是路径上所有的点
while(path[x] != -)
{
q.push(x);
x = edges[path[x]].u;//x变成这条边的起点
}
cout<<u;
while(!q.empty())
{
cout<<"->"<<q.top();
q.pop();
}
cout<<endl;
}
return false;
}
int main()
{
int c;
cin >> n >> c;
int u, v, w;
for(int i = ; i < c; i++)
{
cin >> u >> v >> w;
addedge(u, v, w);
}
if(SPFA())cout<<"存在负环"<<endl;
else cout<<"不存在负环"<<endl;
return ;
}