首页 > 代码库 > SPFA算法
SPFA算法
很多时候给定的图存在负权边,但是Dijkstra算法无能为力,而Bellman-Ford算法的复杂度有过高,
所以就要用到这篇博客讲述的算法——SPFA算法
众所周知 Bellman -Ford 算法会对每条边进行 n - 1 次检查,但是在这些检查过程中,有许多检查是没有必要的.事实上,
唯一应该检查的边存在一个特点:这些边的起点在上一次处理时到源点的距离发生了变化,即松弛成功的边的终点.既然如此,
那么就可以对算法进行优化,即每遍只处理特殊的点,这些点是上一次在松弛过程中某条边的终点.
设立一个先进先出的队列来维护这些待处理的点,优化时每次取出队首节点 u, 并且对所有从点 u 出发的边进行松弛操作,对于每条边的终点 v,
如果以点 v 为终点的边松弛成功, 且 v 不在队列内, 就将点 v 加入队尾.这样不断从对列取出节点来进行松弛操作,
直至队列空为止.这个算法保证只要最短路径存在, SPFA 必定能求出最小值.
有向图
该图片为代码输入的值
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int INF = 0x3f3f3f3f;
const int maxn = 100005;
int head[maxn];
int dist[maxn];
struct node {// 用链式前向星存图
int to;
int w;
int next;
}edge[maxn];
bool SPFA(int s, int n) {//s表示源点,n表示有几个点
int i ,j ,k;
bool visit[maxn];
int outqu[maxn] = {0};//进队的次数
queue<int>qu;
for(i = 0; i <= n; i++) {dist[i] = INF;visit[i] = {false};}//到源点的距离,是否在对内,false表示不在队内
qu.push(s);
visit[s] = true;//在队内
dist[s] = 0;
while(!qu.empty()) {
int temp = qu.front();
qu.pop();
visit[temp] = false;
outqu[temp]++;
if(outqu[temp] > n) return false;//存在负环
for(k = head[temp]; k != -1; k = edge[k].next) {
if(dist[temp]!= INF && dist[edge[k].to] > dist[temp] + edge[k].w) {//进行松弛操作
dist[edge[k].to] = dist[temp] + edge[k].w;
if(!visit[edge[k].to]) {//所指向的点不在队内,则将该点放到队尾
qu.push(edge[k].to);
visit[edge[k].to] = true;
}
}
}
}
return true;
}
int main() {
freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
int n, m, w, i, j;
memset(head, -1, sizeof(head));
cin >> n >> m;//n代表点的个数,m代表边数
for(int k = 1; k <= m; k++) {//链式前向星储存
cin >> i >> j >> w;//i-》j的权值为w
edge[k].to = j;
edge[k].w = w;
edge[k].next = head[i];
head[i] = k;
}
if(SPFA(1,n)) {
cout << dist[2] << endl;
}
else
cout << "error" << endl;
return 0;
}
SPFA算法
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。