算法简介

SPFA算法求解最短路

一句话总结

  • 当边权可能为负的情况下，每个被更新了距离的点都有可能更新它所连的所有点
  • 带着这个思想来看下面的具体步骤吧！（别忘了在纸上比划比划哦~

步骤

  1. 将起始点的dis设为0并放入队列
  2. 获取当前队列的第一个顶点并删除
  3. 对该点的所有连边更新距离
  4. 将step3中被更新了并且不在队中的点入队
  5. 重复step2~4，直到队列为空

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
// SPFA算法
// 主要思想：每个点的距离被更新后都有可能再去更新其他点的距离
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 5e5+10;
int n, m;
int h[MAXN], e[MAXN], ne[MAXN], w[MAXN], cnt, s;
void add(int a, int b, int c) {
    e[cnt] = b, ne[cnt] = h[a], w[cnt] = c, h[a] = cnt++;
}
queue<int> q; // 储存点的序号
int dis[MAXN];
bool vis[MAXN];
void spfa() {
    memset(dis, 0x3f, sizeof dis);
    dis[s] = 0;
    q.push(s), vis[s] = 1;
    while (q.empty() == 0) {
        int u = q.front();
        q.pop();
        vis[u] = 0;
        for(int l = h[u]; l!=-1; l=ne[l]) {
            int v = e[l];
            if((long long)dis[u]+w[l] < dis[v]) { // 防止溢出
                dis[v] = dis[u]+w[l];
                if(!vis[v]) {
                    q.push(v);
                    vis[v] = 1;
                }
            }
        }
    }
}
int main() {
    memset(h, -1, sizeof h);
    cin >> n >> m >> s;
    int a, b, c;
    for(int i=0; i<m; i++) {
        cin >> a >> b >> c;
        add(a, b, c);
    }
    spfa();
    for(int i=1; i<=n; i++) {
        cout << dis[i] << " ";
    }
    cout << endl;
    return 0;
}

缺点

  • SPFA算法中一个点可能多次入队出队，时间复杂度在最劣情况下可能达到O(nm)

优点

  • 随机数据下速度较快（注意看题目数据限制哦）
  • 边长为负时依然正确（与dijkstra对比）

用途

  • 求解有负权边的单源最短路
  • 判读负环（敬请期待~）