算法讲解065 必备 A星、Floyd、Bellman-Fo

来源：算法讲解065【必备】A星、Floyd、Bellman-Ford与SPFA　·　2026-10-31
依据：视频字幕 2000 字

一句话概括

A\* 是带「启发式估价」的 Dijkstra，用于单源单汇最短路；Floyd 是 O(n³) 全源最短路（可带负边）；Bellman-Ford 是「松弛 n−1 轮」的单源最短路（可带负边、可判负环）；SPFA 是 Bellman-Ford 的队列优化版（平均快、最坏退化）。

它解决什么问题

基础知识（前置概念，用大白话解释）

原理（为什么这么做是对的，尽量给直觉）

**A\* 为什么对**：把每个点的键值设为 f(u) = g(u) + h(u)，其中 g(u) 是当前已知 s→u 的距离。若 h 可采纳，则 f(u) 是「经过 u 到 t 的路径长度」的下界。小根堆每次弹出 f 最小的点，当弹出的点是 t 时，它的 g(t) 就是最优——因为任何其他路径的 f 值都不小于当前 f(t) = g(t)（h(t)=0），而 f 又是真实路径长度的下界，所以不可能有更短的。若 h 还满足一致性，则每个点第一次出堆时 g 已最优，等价于「Dijkstra 换了个排序键」。

Floyd 为什么对：f[k][i][j] 表示「只允许经过编号 ≤ k 的中间点」时 i→j 的最短路。转移：f[k][i][j] = min(f[k-1][i][j], f[k-1][i][k] + f[k-1][k][j])——要么不经过 k，要么经过 k。滚动掉第一维就是三重循环 for k: for i: for j: d[i][j] = min(d[i][j], d[i][k]+d[k][j])。k 必须是最外层，因为第 k 层依赖第 k−1 层的完整结果。

Bellman-Ford 为什么对：最短路最多 n−1 条边（无负环时）。第 i 轮松弛保证「边数 ≤ i 的最短路」全部正确。做 n−1 轮即得答案；第 n 轮若还能松弛，说明存在负环。

SPFA 为什么对：Bellman-Ford 每轮把所有边都扫一遍，但只有「上一轮 dist 变小的点」出发的边才可能再松弛。用队列维护这些点即可。正确性同 Bellman-Ford，只是省掉了无效扫描。

步骤（编号，可照着写）

**A\*（网格 4 邻接，曼哈顿距离）**

  1. 读入网格，找起点 s、终点 t。
  2. dist[s]=0，小根堆存 (f, g, x, y)，f = g + h。
  3. 弹出堆顶；若已访问过该点则跳过；标记访问。
  4. 若是 t，返回 g。
  5. 对 4 个邻居：若可走且 g + w < dist[nx][ny]，更新 dist，入堆 (dist + h, dist, nx, ny)。
  6. 堆空仍未到 t ⇒ 不可达。

Floyd

  1. d[i][j] = w(i,j)，无边为 INF，d[i][i]=0。
  2. for k in 0..n-1: for i: for j: d[i][j] = min(d[i][j], d[i][k]+d[k][j])。
  3. 输出 d。判负环：存在 i 使 d[i][i] < 0。

Bellman-Ford

  1. dist[s]=0，其余 INF。
  2. 重复 n−1 轮：遍历所有边 (u,v,w)，若 dist[u]+w < dist[v] 则更新。
  3. 再扫一遍所有边，若还能更新 ⇒ 负环。

SPFA

  1. dist[s]=0，inqueue[s]=true，队列 push s。
  2. 弹出 u，inqueue[u]=false；对每条出边 (u,v,w)：若 dist[u]+w < dist[v]，更新；若 v 不在队列，push 并标记。记录 cnt[v]（入队次数），若 cnt[v] ≥ n ⇒ 负环。
  3. 队列空结束。

样例（一个具体小例子，带每步变化）

网格（. 可走，# 墙），s=(0,0)，t=(2,2)，4 邻接，每步代价 1，h = 曼哈顿距离：

. . .
# . .
. . .

A\* 过程（堆中元素 (f,g,pos)）：

| 步 | 弹出 | g | 新入堆 |

|---|---|---|---|

| 1 | (4,0,(0,0)) | 0 | (5,1,(0,1)), (5,1,(1,0)) |

| 2 | (5,1,(0,1)) | 1 | (5,2,(0,2)), (6,2,(1,1)) |

| 3 | (5,2,(0,2)) | 2 | (6,3,(1,2)) |

| 4 | (6,2,(1,1)) | 2 | (6,3,(2,1)) |

| 5 | (6,3,(1,2)) | 3 | (6,4,(2,2)) |

| 6 | (6,4,(2,2)) | 4 | 弹出 t，答案 4 |

对比 Dijkstra 会先扩展 (1,0) 等「远离目标」的点，A\* 因 f 值更小优先走靠近 t 的方向。

代码（Python 一份：好读、用于理解；C++ 一份：竞赛风，能直接抄进比赛，带注释，不用玄学宏）

**Python（A\* 网格）**

import heapq

def astar(grid, s, t):
    n, m = len(grid), len(grid[0])
    def h(x, y): return abs(x - t[0]) + abs(y - t[1])
    INF = float('inf')
    dist = [[INF]*m for _ in range(n)]
    dist[s[0]][s[1]] = 0
    pq = [(h(*s), 0, s[0], s[1])]
    vis = [[False]*m for _ in range(n)]
    while pq:
        f, g, x, y = heapq.heappop(pq)
        if vis[x][y]: continue
        vis[x][y] = True
        if (x, y) == t: return g
        for dx, dy in ((1,0),(-1,0),(0,1),(0,-1)):
            nx, ny = x+dx, y+dy
            if 0 <= nx < n and 0 <= ny < m and grid[nx][ny] != '#' and not vis[nx][ny]:
                ng = g + 1
                if ng < dist[nx][ny]:
                    dist[nx][ny] = ng
                    heapq.heappush(pq, (ng + h(nx, ny), ng, nx, ny))
    return -1

Python（Floyd）

def floyd(d):  # d[i][j] 已初始化，无边 INF，d[i][i]=0
    n = len(d)
    for k in range(n):
        for i in range(n):
            dik = d[i][k]
            if dik == float('inf'): continue
            for j in range(n):
                if dik + d[k][j] < d[i][j]:
                    d[i][j] = dik + d[k][j]
    return d

Python（SPFA）

from collections import deque
def spfa(n, adj, s):
    INF = float('inf')
    dist = [INF]*n; dist[s] = 0
    inq = [False]*n; cnt = [0]*n
    q = deque([s]); inq[s] = True
    while q:
        u = q.popleft(); inq[u] = False
        for v, w in adj[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                cnt[v] += 1
                if cnt[v] >= n: return None  # 负环
                if not inq[v]:
                    q.append(v); inq[v] = True
    return dist

**C++（A\* 网格，竞赛风）**

#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
int n, m;
vector<string> g;
int sx, sy, tx, ty;

int h(int x, int y) { return abs(x - tx) + abs(y - ty); }

int astar() {
    vector<vector<int>> dist(n, vector<int>(m, INF));
    vector<vector<char>> vis(n, vector<char>(m, 0));
    // (f, g, x, y)，小根堆
    priority_queue<tuple<int,int,int,int>, vector<tuple<int,int,int,int>>, greater<>> pq;
    dist[sx][sy] = 0;
    pq.emplace(h(sx, sy), 0, sx, sy);
    int dx[4] = {1,-1,0,0}, dy[4] = {0,0,1,-1};
    while (!pq.empty()) {
        auto [f, d, x, y] = pq.top(); pq.pop();
        if (vis[x][y]) continue;
        vis[x][y] = 1;
        if (x == tx && y == ty) return d;
        for (int k = 0; k < 4; ++k) {
            int nx = x + dx[k], ny = y + dy[k];
            if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
            if (g[nx][ny] == '#' || vis[nx][ny]) continue;
            int nd = d + 1;
            if (nd < dist[nx][ny]) {
                dist[nx][ny] = nd;
                pq.emplace(nd + h(nx, ny), nd, nx, ny);
            }
        }
    }
    return -1;
}

C++（Floyd，滚动一维，注意 long long）

const long long INF = 0x3f3f3f3f3f3f3f3fLL;
void floyd(vector<vector<long long>>& d) {
    int n = d.size();
    for (int k = 0; k < n; ++k)
        for (int i = 0; i < n; ++i) {
            if (d[i][k] == INF) continue;          // 剪枝
            long long dik = d[i][k];
            for (int j = 0; j < n; ++j)
                if (dik + d[k][j] < d[i][j]) d[i][j] = dik + d[k][j];
        }
}

C++（Bellman-Ford，边表）

struct Edge { int u, v; long long w; };
// 返回 false 表示存在从 s 可达的负环
bool bellman(int n, const vector<Edge>& es, int s, vector<long long>& dist) {
    const long long INF = 0x3f3f3f3f3f3f3f3fLL;
    dist.assign(n, INF); dist[s] = 0;
    for (int it = 0; it < n - 1; ++it) {
        bool upd = false;
        for (auto& e : es)
            if (dist[e.u] != INF && dist[e.u] + e.w < dist[e.v]) {
                dist[e.v] = dist[e.u] + e.w; upd = true;
            }
        if (!upd) break;                            // 提前退出
    }
    for (auto& e : es)
        if (dist[e.u] != INF && dist[e.u] + e.w < dist[e.v]) return false;
    return true;
}

C++（SPFA，vector 邻接表）

// 返回 false 表示存在从 s 可达的负环
bool spfa(int n, const vector<vector<pair<int,long long>>>& adj, int s, vector<long long>& dist) {
    const long long INF = 0x3f3f3f3f3f3f3f3fLL;
    dist.assign(n, INF); dist[s] = 0;
    vector<char> inq(n, 0);
    vector<int> cnt(n, 0);
    queue<int> q; q.push(s); inq[s] = 1;
    while (!q.empty()) {
        int u = q.front(); q.pop(); inq[u] = 0;
        for (auto [v, w] : adj[u]) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                if (++cnt[v] >= n) return false;    // 入队 ≥ n 次 ⇒ 负环
                if (!inq[v]) { q.push(v); inq[v] = 1; }
            }
        }
    }
    return true;
}

复杂度（时间/空间，最好/平均/最坏，顺带说常数大不大）

| 算法 | 时间 | 空间 | 常数 |

|---|---|---|---|

| A\* | 取决于 h；h 越准越快，最坏同 Dijkstra O((V+E)logV) | O(V+E) | 堆操作，常数中等 |

| Floyd | O(n³)，最好=最坏 | O(n²) | 三重循环，常数小，n≤500 可过 |

| Bellman-Ford | O(VE)，最好 O(E)（一轮无更新） | O(V+E) | 小 |

| SPFA | 平均 O(kE)，最坏 O(VE)（网格图/菊花图易被卡） | O(V+E) | 小，但可被构造数据卡到 TLE |

竞赛里什么时候用（看到什么题面特征就该想到它）

竞赛模板（C++，可直接背下来的写法；变量名清楚）

// ===== Floyd：n ≤ 500，long long 防溢出 =====
const long long INF = 0x3f3f3f3f3f3f3f3fLL;
void floyd(vector<vector<long long>>& d) {
    int n = d.size();
    for (int k = 0; k < n; ++k)
        for (int i = 0; i < n; ++i) {
            if (d[i][k] == INF) continue;
            for (int j = 0; j < n; ++j)
                if (d[i][k] + d[k][j] < d[i][j])
                    d[i][j] = d[i][k] + d[k][j];
        }
}

// ===== SPFA：返回 false 表示有从 s 可达的负环 =====
bool spfa(int n, const vector<vector<pair<int,long long>>>& adj, int s, vector<long long>& dist) {
    dist.assign(n, INF); dist[s] = 0;
    vector<char> inq(n, 0);
    vector<int> cnt(n, 0);
    queue<int> q; q.push(s); inq[s] = 1;
    while (!q.empty()) {
        int u = q.front(); q.pop(); inq[u] = 0;
        for (auto [v, w] : adj[u])
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                if (++cnt[v] >= n) return false;
                if (!inq[v]) q.push(v), inq[v] = 1;
            }
    }
    return true;
}

边界与易错点（WA 的常见原因，越具体越好）

同类题 / 变形（说清楚怎么改）

常见坑

拓展（变体、实际用途、面试常问）

自测 3 题（题目 + 折叠答案）

题 1：n=4 的有向图，边 0→1 (1), 1→2 (-2), 2→3 (1), 3→1 (1)，从 0 出发，判断是否有负环，若有输出 -1。

答案

环 1→2→3→1 权和 -2+1+1=0，非负环。但注意 0→1→2→3→1 绕一圈回到 1 距离不变，无负环。dist = [0, 1, -1, 0]。SPFA 中 cnt[1] 会到 2 但 < 4，正常结束。结论：无负环。

</details>

题 2：3×3 网格，s=(0,0)，t=(2,2)，中间 (1,1) 是墙，4 邻接，每步 1。用 A\*（曼哈顿 h）求最短路长度，并说明为什么 A\*