问题描述

给定一个 n 个点 m 条边的有向图（或无向图），每条边有一个权值 w，求从源点 s 到其他所有点的最短路径长度。

Dijkstra 算法

适用范围

非负权图，即所有边的权值 w ≥ 0。

算法思想

Dijkstra 是一种贪心算法。维护一个集合 S，表示已经确定最短路的点。初始时 S = {s}，dis(s) = 0。

每次从未确定的点中选出 dis 值最小的点 u，将其加入 S，然后用 u 的出边更新邻居的 dis 值：

dis(v) = min  (dis(v), dis(u) + w(u, v))

这个过程称为松弛（relaxation）。

正确性

证明（简要）

每次选出的 u 的 dis 值已经是最短路。反证法：如果存在更短的路径，该路径上必经过某个不在 S 中的点 v，而 dis(v) ≥ dis(u)（因为 u 是 dis 最小的），加上后续边权  ≥ 0，所以路径长度  ≥ dis(u)，矛盾。

这也是为什么 Dijkstra 不能处理负权边的原因：如果有负边权，上述不等式不成立。

朴素实现

每次暴力扫描所有点找最小值，时间复杂度 O(n2 + m)。适用于稠密图（m ∼ n2）。

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
#include <bits/stdc++.h>
using lint = long long;
const lint INF = 1e18;
const int N = 5e3 + 10;

int n, m, s;
lint dis[N];
bool vis[N];
std::vector<std::pair<int, lint>> G[N];

void dijkstra() {
  std::fill(dis + 1, dis + n + 1, INF);
  dis[s] = 0;
  for (int i = 1; i <= n; ++i) {
    int u = 0;
    for (int j = 1; j <= n; ++j)
      if (!vis[j] && (!u || dis[j] < dis[u])) u = j;
    vis[u] = true;
    for (auto [v, w] : G[u])
      if (dis[u] + w < dis[v])
        dis[v] = dis[u] + w;
  }
}

int main() {
  std::cin.tie(0)->sync_with_stdio(0);
  std::cin >> n >> m >> s;
  for (int i = 0, u, v; i < m; ++i) {
    lint w;
    std::cin >> u >> v >> w;
    G[u].push_back({v, w});
  }
  dijkstra();
  for (int i = 1; i <= n; ++i)
    std::cout << dis[i] << " \n"[i == n];
  std::cout.flush();
  return 0;
}

堆优化

用优先队列（小根堆）维护待松弛的点，每次取出 dis 最小的点。

时间复杂度 O((n + m)log m)，适用于稀疏图。

例题：洛谷 P4779 【模板】单源最短路径（标准版）。

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
#include <bits/stdc++.h>
using lint = long long;
using pli = std::pair<lint, int>;
const lint INF = 1e18;
const int N = 1e5 + 10;

int n, m, s;
lint dis[N];
std::vector<std::pair<int, lint>> G[N];

void dijkstra() {
  std::fill(dis + 1, dis + n + 1, INF);
  dis[s] = 0;
  std::priority_queue<pli, std::vector<pli>, std::greater<pli>> pq;
  pq.push({0, s});
  while (!pq.empty()) {
    auto [d, u] = pq.top(); pq.pop();
    if (d > dis[u]) continue; // 已经被更优的路径更新过
    for (auto [v, w] : G[u]) {
      if (dis[u] + w < dis[v]) {
        dis[v] = dis[u] + w;
        pq.push({dis[v], v});
      }
    }
  }
}

int main() {
  std::cin.tie(0)->sync_with_stdio(0);
  std::cin >> n >> m >> s;
  for (int i = 0, u, v; i < m; ++i) {
    lint w;
    std::cin >> u >> v >> w;
    G[u].push_back({v, w});
  }
  dijkstra();
  for (int i = 1; i <= n; ++i)
    std::cout << dis[i] << " \n"[i == n];
  std::cout.flush();
  return 0;
}

关于 if (d > dis[u]) continue;

一个点可能被多次加入优先队列（每次被松弛都会入队）。当取出时发现 d > dis(u)，说明已经有更优的路径更新过了，直接跳过。

这个判断是保证复杂度的关键。

SPFA 算法

适用范围

任意权图（可以有负权边），但不能有负环。如果需要判断负环，SPFA 也能胜任。

算法思想

SPFA（Shortest Path Faster Algorithm）是 Bellman-Ford 的队列优化。

维护一个队列，初始将源点入队。每次取出队首 u，用 u 的出边松弛邻居 v。如果 v 被成功松弛且 v 不在队列中，则将 v 入队。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
lint dis[N];
bool inq[N];
int cnt[N]; // 用于判负环

bool spfa() {
  std::fill(dis + 1, dis + n + 1, INF);
  dis[s] = 0;
  std::queue<int> q;
  q.push(s); inq[s] = true;
  while (!q.empty()) {
    int u = q.front(); q.pop();
    inq[u] = false;
    for (auto [v, w] : G[u]) {
      if (dis[u] + w < dis[v]) {
        dis[v] = dis[u] + w;
        cnt[v] = cnt[u] + 1;
        if (cnt[v] >= n) return false; // 存在负环
        if (!inq[v]) q.push(v), inq[v] = true;
      }
    }
  }
  return true;
}

复杂度

SPFA 的最坏时间复杂度为 O(nm)，与 Bellman-Ford 相同。

关于 SPFA：它死了。

在竞赛中，出题人可以构造数据将 SPFA 卡到 O(nm)。因此在非负权图上应始终使用 Dijkstra，只有在存在负权边时才考虑 SPFA。

判负环

若某个点被松弛了 n 次以上（即从源点到它经过了  ≥ n 条边），则说明存在负环。用 cnt[v] 记录即可。

各算法对比

算法 时间复杂度 负权边 负环判断
朴素 Dijkstra O(n2) ❌ ❌
堆优化 Dijkstra O((n + m)log m) ❌ ❌
SPFA O(nm)（最坏） ✅ ✅
Bellman-Ford O(nm) ✅ ✅
Floyd O(n3) ✅ ✅

一般来说，非负权图用堆优化 Dijkstra，有负权边时用 SPFA / Bellman-Ford，全源最短路用 Floyd。

Floyd 算法

晚点写。