以下摘要由GPT-4o生成:
SPFA（Shortest Path Faster Algorithm）是一种针对最短路径问题的高效算法，特别适用于处理含有负权边的图。其核心思想是通过动态选择可能优化路径的节点进行松弛，避免冗余操作。与Dijkstra算法相比，SPFA允许节点多次入队和处理，从而能及时更新路径长度，尤其在遇到负权边时表现出更好的灵活性。然而，如果图中存在负权环，SPFA可能会出现死循环，因此需要额外判断。整体而言，SPFA通过“按需松弛”提高了效率，适应性强，但在使用时需关注负权环的问题。

题目链接[1.蓝桥公园 - 单源最短路径]

floyd

时间复杂度O(n ^ n ^ n) n == 100左右

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
#include <cstdio>
#include <cstring>
#include <iostream>
int n, m, q;
const int N = 410, INF = 0x3f3f3f3f;
int g[N][N];

void floyd(){
    for (int k = 1; k <= n; k++) {
      for (int i = 1; i <= n; i++) {
        for (int j = 1; j <=n; j++ ) {
          if (g[i][j] > g[i][k] + g[k][j])
            g[i][j] = g[i][k] + g[k][j];
        }
      }
    }
}


int main(){

  memset(g, 0x3f,sizeof g);
  scanf("%d%d%d", &n, &m, &q);
  for (int i = 1; i <= n; i ++) g[i][i] = 0;//处理自环；i -> k -> j时k == i的情况;
  
  while ( m -- ) {
    int a, b, c;
    scanf("%d%d%d", &a, &b, &c);
    if (c < g[a][b]) {
      g[a][b] = c;
      g[b][a] = c;//最小权边;
    }
  }
  floyd();
  while (q -- ) {
    int u, v;
    scanf("%d%d", &u, &v);
    if (g[u][v] == INF) printf("-1\n"); // 不可达
    else printf("%d\n", g[u][v]);
  }

  return 0;
}

dijkstra

间复杂度O(n ^ n × log(m)),n为点，m为边数

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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <iostream>
#include <cstring>
using namespace std;

const int N = 410;
const int INF = 0x3f3f3f3f;
int n, m, q;
int g[N][N]; // 邻接矩阵存储图
bool st[N];  // 标记是否已确定最短路
int dist[N]; // 距离数组

// Dijkstra算法：计算从u到v的最短路径
int dijkstra(int u, int v) {
    memset(dist, 0x3f, sizeof dist);
    memset(st, 0, sizeof st);
    dist[u] = 0; // 起点距离初始化为0

    // 迭代n-1次，确定每个节点的最短路径
    for (int i = 0; i < n - 1; i++) {
        int t = -1; // 当前未确定最短路的最小距离节点
        for (int j = 1; j <= n; j++) {
            if (!st[j] && (t == -1 || dist[j] < dist[t])) {
                t = j;
            }
        }
        if (t == -1) break; // 无可达节点，提前退出
        st[t] = true; // 标记为已确定

        // 更新所有节点的距离
        for (int j = 1; j <= n; j++) {
            if (dist[j] > dist[t] + g[t][j]) {
                dist[j] = dist[t] + g[t][j];
            }
        }
    }
    return dist[v] == INF ? -1 : dist[v]; // 返回结果
}

int main() {
    scanf("%d%d%d", &n, &m, &q);
    
    // 初始化邻接矩阵为无穷大，自环为0
    memset(g, 0x3f, sizeof g);
    for (int i = 1; i <= n; i++) g[i][i] = 0;

    // 读取边并更新邻接矩阵（假设为无向图）
    while (m--) {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        if (c < g[a][b]) { // 处理重边，保留最小权重
            g[a][b] = c;
            g[b][a] = c;
        }
    }

    // 处理多组查询
    while (q--) {
        int u, v;
        scanf("%d%d", &u, &v);
        printf("%d\n", dijkstra(u, v)); // 调用Dijkstra
    }

    return 0;
}

优化版dijkstra(priority_queue)

堆化优化后为：O(m × log(n)）

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
50
51
52
53
54
55
56
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
const int N = 3e5 +10, M = 1e6, INF = 0x3f3f3f3f;
int n, m;
int dist[N];
bool st[N];
int e[M], h[N], ne[M], idx, w[M];//链式前向星;
typedef pair<int, int> PII;

void add(int a,int b, int c) {
  e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++; 
}
void dijkstra() {
    memset(dist, 0x3f, sizeof dist);
    priority_queue <PII, vector<PII>, greater<PII>> pq;
    dist[1] = 0;//从1开始;
    pq.push({0, 1}); //first表示单源最短距离，second表示当前节点
    while (!pq.empty()) {
      auto t = pq.top();
      pq.pop();
      int ver = t.second, distance = t.first;
      if (st[ver]) continue;//当前点已经添加过;
      st[ver] = true;
      for (int i = h[ver]; ~i; i = ne[i]) {
          int j = e[i];
          if (dist[j] > distance + w[i])
            {
              dist[j] = distance + w[i];
              pq.push({dist[j], j});
          }
      }
    }
    //return dist[n] == INF ? -1 : dist[n];
}


int main() {
    memset(h, -1, sizeof h);
    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; ++i) {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        add(u, v, w); // 单向边处理
    }
    dijkstra();
    
    for (int i = 1; i <= n; ++i) {
        if (i > 1) printf(" ");
        printf("%d", dist[i] == INF ? -1 : dist[i]);
    }
    printf("\n");
    return 0;
}

处理负权边-spfa

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
int n;      // 总点数
int h[N], w[N], e[N], ne[N], idx;       // 邻接表存储所有边
int dist[N];        // 存储每个点到1号点的最短距离
bool st[N];     // 存储每个点是否在队列中

// 求1号点到n号点的最短路距离，如果从1号点无法走到n号点则返回-1
int spfa()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;

    queue<int> q;
    q.push(1);
    st[1] = true;

    while (q.size())
    {
        auto t = q.front();
        q.pop();

        st[t] = false;

        for (int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > dist[t] + w[i])
            {
                dist[j] = dist[t] + w[i];
                if (!st[j])     // 如果队列中已存在j，则不需要将j重复插入
                {
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }

    if (dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];
}

SPFA（Shortest Path Faster Algorithm）的核心思想是动态选择可能优化最短路径的节点进行松弛，避免全局遍历所有边的冗余操作。其核心机制与Dijkstra的贪心策略不同，具体思想可通过以下步骤拆解：

SPFA的核心思想

  1. 松弛驱动的动态更新

    • 只处理可能缩短路径的节点。当一个节点被松弛成功（即发现更短的路径）时，才将其加入队列等待后续处理。
    • 与Dijkstra的“一次性确定最短路径”不同，SPFA允许节点多次入队，确保所有可能的路径优化都被探索。

  2. 队列维护待处理节点

    • 使用普通队列（而非优先队列）管理待处理的节点，遵循先进先出原则。
    • 节点出队时，尝试松弛其邻接边；若邻接点距离被更新且不在队列中，则将其入队。

  3. 处理负权边的能力

    • 由于允许节点多次松弛，即使存在负权边导致路径反复缩短，SPFA仍能正确更新距离。
    • 但图中若存在负权环，SPFA会陷入死循环（需额外判断环的存在）。

与Dijkstra算法的对比

特性 Dijkstra SPFA
策略 贪心选择当前距离最小的节点 动态处理可能被松弛的节点
数据结构 优先队列（最小堆） 普通队列
节点处理次数 每个节点仅处理一次 节点可能多次入队
负权边支持 ❌ 无法处理 ✅ 支持（无负权环时）
时间复杂度 O(m log n)（堆优化） 平均O(m)，最坏O(nm)
适用场景 边权非负的图 含负权边但无负权环的图

举例说明

假设节点A的最短距离初始为5，后续发现一条通过负权边的路径使其距离变为3：

  • Dijkstra：已处理过A，不再更新，导致错误。
  • SPFA：将A重新入队，继续松弛其邻接边，最终得到正确的最短距离。

SPFA的关键优势

  • 高效性：通过队列减少冗余松弛，实际运行效率接近BFS。
  • 灵活性：支持负权边，弥补了Dijkstra的不足。
  • 动态性：每次只处理可能影响后续路径的节点，避免全局遍历。

总结

SPFA的思想是“按需松弛”，通过队列动态管理需要更新的节点，确保每次操作都是必要的。与Dijkstra的“贪心固化路径”不同，SPFA的灵活性使其能处理更复杂的图结构（如含负权边），但需注意负权环的检测。两者本质区别在于是否允许节点重复参与路径优化，这决定了它们在不同场景下的适用性。