首页 > 代码库 > SPFA算法

SPFA算法

2024-09-12 10:31:48   216人阅读

很多时候给定的图存在负权边，但是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算法


联系
我们