Dijkstra：当每一步的代价不同

问题：最短的路不一定最快

上一篇的 BFS 找的是步数最少的路径。但在真实的游戏地图上，格子和格子并不一样：走平地一步花 1 秒，穿过森林要 3 秒，蹚过沼泽要 6 秒。

一个士兵要从 S 走到 G，中间横着一片沼泽。BFS 会毫不犹豫地直穿过去，因为这样步数最少；而任何一个玩过策略游戏的人都知道，绕到下面走平地更快。

我们需要的是总代价最小的路径。解决这个问题的经典算法，是 Edsger Dijkstra 在 1956 年提出的最短路径算法。

从 BFS 出发

回忆一下 BFS 为什么是对的：它按距离由近到远的顺序访问格子，所以一个格子第一次被访问时，走的一定是最短的路。

当每一步代价都是 1 时，“先入队的格子离起点更近”天然成立，先进先出队列刚好就是按距离排序的。一旦代价不同，这个性质就被打破了：一个格子虽然先入队，但可能是踩着沼泽进来的，它的总代价反而比后入队的格子更大。

Dijkstra 的修改只有一处：把先进先出队列换成优先队列，每次取出的不是“最早发现的”格子，而是”目前已知总代价最小“的格子。

	BFS	Dijkstra
边界的数据结构	先进先出队列	优先队列（小顶堆）
每次取出	最早发现的格子	已知代价最小的格子
记录	是否访问过	目前已知的最小代价 costSoFar
找到更短的路时	不会发生	更新代价，重新入堆

亲手试一试

图 1.2顶部选择画笔，在格子上拖动绘制地形；拖动 S、G 改变起点和终点。数字是到起点的总代价，虚线是同一张地图上 BFS 的路径。单独打开 ↗

和 BFS 演示相比，画面多了两种地形：

图例	含义
四角的点	森林，进入代价 3
上下两组横线	沼泽，进入代价 6
沙色渐变	代价已经确定的格子，数字是到起点的最小总代价
赭黄方块	边界：已发现、代价还可能被改小的格子
朱红线 / 墨色虚线	Dijkstra 的路径 / BFS 的路径

几个值得做的小实验：

1. 右上角会同时显示两条路径的总代价。默认地图上 BFS 直穿沼泽，代价 37；Dijkstra 绕到下方，代价 30。
2. 单步执行，注意边界不再是一圈“等步数线”。它在平地上推进得快，在沼泽前面停滞不前，形状像水流绕开了障碍。
3. 选择 erase 画笔，在沼泽带上擦出一条平地通道。路径会立即改走通道，总代价随之下降。
4. 把整张地图都涂成沼泽，Dijkstra 的边界又会变回 BFS 那样的菱形：代价全部相同时，两者完全等价。

实现

带代价的地图

在 BFS 的 Grid 上再加一层代价。约定代价是”走进这个格子要花多少”，所以从平地走进沼泽花 6，从沼泽走回平地只花 1。

cpp/common/cost_grid.h

// 带地形代价的网格：在 Grid（墙 / 空地）的基础上，给每个格子加一个"走进来要花多少"。
// 继承 Grid，所以 BFS 可以直接跑在它上面（只是会无视代价）。
class CostGrid : public Grid {
public:
    CostGrid(int width, int height) : Grid(width, height), costs_(static_cast<size_t>(width * height), 1) {}

    // 进入格子 c 的代价，约定 >= 1
    int cost(Cell c) const { return costs_[index(c)]; }
    void setCost(Cell c, int cost) { costs_[index(c)] = cost; }

private:
    std::vector<int> costs_;
};

核心循环

cpp/pathfinding/dijkstra/dijkstra.h

// Dijkstra：返回从 start 到 goal 总代价最小的路径，不可达时返回空
inline std::vector<Cell> dijkstraPath(const CostGrid& grid, Cell start, Cell goal) {
    if (!grid.passable(start) || !grid.passable(goal)) return {};

    std::vector<int> costSoFar(grid.size(), kUnreached);  // 目前已知的最小代价
    std::vector<int> cameFrom(grid.size(), -1);

    // 小顶堆：每次取出"已知代价最小"的格子。条目是 (代价, 格子下标)
    using Entry = std::pair<int, int>;
    std::priority_queue<Entry, std::vector<Entry>, std::greater<Entry>> frontier;

    int s = grid.index(start);
    costSoFar[s] = 0;
    cameFrom[s] = s;
    frontier.push({0, s});

    while (!frontier.empty()) {
        auto [cost, ci] = frontier.top();
        frontier.pop();
        if (cost > costSoFar[ci]) continue;  // 过期条目：这个格子后来找到了更便宜的路

        Cell current = grid.cellAt(ci);
        if (current == goal) break;  // 终点出堆时，它的代价就是最终答案

        grid.forEachNeighbor(current, [&](Cell next) {
            int ni = grid.index(next);
            int newCost = cost + grid.cost(next);
            if (newCost < costSoFar[ni]) {  // 松弛：找到了一条更便宜的路
                costSoFar[ni] = newCost;
                cameFrom[ni] = ci;
                frontier.push({newCost, ni});
            }
        });
    }
    return reconstructPath(grid, cameFrom, start, goal);
}

和 BFS 逐行对照，变化只有三处：

• frontier 是一个按代价排序的小顶堆。std::priority_queue 默认是大顶堆，所以要传入 std::greater。
• 用 costSoFar 代替“是否访问过”。一个格子即使已经在边界里，只要发现了一条更便宜的路，就更新它的代价和来路。这一步叫做松弛（relaxation）。
• 出堆时检查条目是否过期，下面单独解释。

为什么要跳过过期条目

一个格子可能被多次加入堆：先以代价 15 入堆，后来又找到了代价 12 的路，再以 12 入堆。std::priority_queue 不支持修改已有元素，于是堆里同时存在 (15, x) 和 (12, x) 两条记录。

(12, x) 会先出堆并被正常处理。等到 (15, x) 出堆时，costSoFar[x] 已经是 12，这条记录已经没有意义，直接跳过即可。这种做法叫做惰性删除（lazy deletion），代价是堆会稍微大一点，换来的是可以直接使用标准库。

不跳过会怎样

结果仍然正确，但一个格子会被重复展开多次，用过期的大代价去松弛邻居，白白浪费时间。在代价差异大的地图上，展开次数可能翻倍。

为什么终点出堆时就可以停

Dijkstra 正确性的关键在于：一个格子出堆时，它的代价已经是最终答案。

假设格子 x 以代价 c 出堆，却存在一条更便宜的路。这条路上一定有某个格子还在堆里（否则 x 早就被它松弛成更小的值了），而它的代价小于 c，那它应该比 x 先出堆，矛盾。

这个论证依赖一个前提：代价不能是负数。如果走进某个格子能“返还”时间，后面的格子就可能把前面已经确定的代价再改小，整个推理就不成立了。游戏地图的代价几乎总是正数，所以这一点很少成为问题；真的需要负代价时，要换用 Bellman-Ford 算法。

单步版本

演示用的是同样的逻辑。为了把边界画出来，需要能遍历堆里的元素，所以用 vector 加 std::push_heap / std::pop_heap 手动维护堆，效果与 priority_queue 完全一样。

cpp/pathfinding/dijkstra/dijkstra.h

// 可单步执行的 Dijkstra，逻辑与 dijkstraPath 一致。
// 为了能遍历边界画出来，用 vector + std::push_heap / pop_heap 代替 priority_queue（二者等价）。
class DijkstraStepper {
public:
    DijkstraStepper(const CostGrid& grid, Cell start, Cell goal)
        : grid_(&grid), start_(start), goal_(goal),
          costSoFar_(grid.size(), kUnreached), cameFrom_(grid.size(), -1), closed_(grid.size(), 0) {
        if (grid.passable(start) && grid.passable(goal)) {
            int s = grid.index(start);
            costSoFar_[s] = 0;
            cameFrom_[s] = s;
            push({0, s});
        }
    }

    // 执行一步：取出代价最小的格子并松弛它的邻居。搜索结束时返回 false
    bool step() {
        while (!heap_.empty()) {
            Entry top = pop();
            if (top.first > costSoFar_[top.second]) continue;  // 跳过过期条目，不算一步

            int ci = top.second;
            current_ = grid_->cellAt(ci);
            hasCurrent_ = true;
            closed_[ci] = 1;
            ++expanded_;
            if (current_ == goal_) {
                found_ = true;
                return false;
            }
            grid_->forEachNeighbor(current_, [&](Cell next) {
                int ni = grid_->index(next);
                int newCost = top.first + grid_->cost(next);
                if (newCost < costSoFar_[ni]) {
                    if (costSoFar_[ni] != kUnreached) ++relaxed_;  // 已在边界上的格子被改得更便宜
                    costSoFar_[ni] = newCost;
                    cameFrom_[ni] = ci;
                    push({newCost, ni});
                }
            });
            return !done();
        }
        return false;
    }

    bool done() const { return found_ || liveFrontierSize() == 0; }
    bool found() const { return found_; }
    bool hasCurrent() const { return hasCurrent_; }
    Cell current() const { return current_; }
    int expandedCount() const { return expanded_; }
    int relaxedCount() const { return relaxed_; }
    int cost(Cell c) const { return costSoFar_[grid_->index(c)]; }  // kUnreached = 未发现
    bool closed(Cell c) const { return closed_[grid_->index(c)] != 0; }

    // 边界上仍然有效的格子（过滤掉过期条目）
    template <class F>
    void forEachFrontier(F&& visit) const {
        for (const Entry& e : heap_) {
            if (e.first == costSoFar_[e.second] && !closed_[e.second]) visit(grid_->cellAt(e.second));
        }
    }
    int liveFrontierSize() const {
        int n = 0;
        forEachFrontier([&](Cell) { ++n; });
        return n;
    }

    std::vector<Cell> path() const {
        return found_ ? reconstructPath(*grid_, cameFrom_, start_, goal_) : std::vector<Cell>{};
    }

private:
    using Entry = std::pair<int, int>;
    void push(Entry e) {
        heap_.push_back(e);
        std::push_heap(heap_.begin(), heap_.end(), std::greater<Entry>{});
    }
    Entry pop() {
        std::pop_heap(heap_.begin(), heap_.end(), std::greater<Entry>{});
        Entry e = heap_.back();
        heap_.pop_back();
        return e;
    }

    const CostGrid* grid_;
    Cell start_, goal_;
    std::vector<int> costSoFar_;
    std::vector<int> cameFrom_;
    std::vector<char> closed_;
    std::vector<Entry> heap_;
    Cell current_{};
    bool hasCurrent_ = false;
    bool found_ = false;
    int expanded_ = 0;
    int relaxed_ = 0;
};

Dijkstra 地图：一次计算，所有人共用

去掉“找到终点就停”这一行，从源点出发跑完整张图，就得到了每个格子到源点的最小代价。如果一开始把多个源点都放进堆里，得到的就是每个格子到”最近的那个源点“的代价。

cpp/pathfinding/dijkstra/dijkstra.h

// Dijkstra 地图：从一个或多个源点出发跑完整张图，得到每个格子到"最近源点"的代价。
// 不可达的格子为 kUnreached。
inline std::vector<int> dijkstraMap(const CostGrid& grid, const std::vector<Cell>& sources) {
    std::vector<int> costSoFar(grid.size(), kUnreached);
    using Entry = std::pair<int, int>;
    std::priority_queue<Entry, std::vector<Entry>, std::greater<Entry>> frontier;

    for (Cell c : sources) {
        if (!grid.passable(c)) continue;
        costSoFar[grid.index(c)] = 0;
        frontier.push({0, grid.index(c)});
    }
    while (!frontier.empty()) {
        auto [cost, ci] = frontier.top();
        frontier.pop();
        if (cost > costSoFar[ci]) continue;
        grid.forEachNeighbor(grid.cellAt(ci), [&](Cell next) {
            int ni = grid.index(next);
            int newCost = cost + grid.cost(next);
            if (newCost < costSoFar[ni]) {
                costSoFar[ni] = newCost;
                frontier.push({newCost, ni});
            }
        });
    }
    return costSoFar;
}

// 沿着 Dijkstra 地图"下坡"走一步：选择代价最小的邻居。已经在源点或无路可走时返回 from
inline Cell rollDownhill(const CostGrid& grid, const std::vector<int>& map, Cell from) {
    Cell best = from;
    grid.forEachNeighbor(from, [&](Cell next) {
        if (map[grid.index(next)] < map[grid.index(best)]) best = next;
    });
    return best;
}

这张表在 Roguelike 社区里被称为 Dijkstra 地图。有了它，单位不需要各自寻路，每一步只要走向代价更小的邻居（rollDownhill），就一定能走到最近的源点。用法非常灵活：

• 追击：以玩家为源点，所有怪物沿下坡走，就能包围玩家。
• 逃跑：把追击地图的每个值乘以 -1.2 左右，以此为初始值再扫描一遍，怪物会逃向“离玩家远、又不会被逼进死角”的地方。
• 找资源：以所有矿点为源点，农民沿下坡走，自动去最近的矿。
• 组合欲望：把多张地图按权重相加，例如“想去拿宝箱，但又怕靠近玩家”。

后面的“流场寻路”一章，就是这个想法在 RTS 中的应用。

复杂度与常见陷阱

设地图有 V 个格子、E 条相邻关系。每次松弛最多入堆一次，堆操作是 O(log V)：

• 时间复杂度 O((V + E) log V)
• 空间复杂度 O(V + E)：costSoFar、cameFrom，加上可能含有过期条目的堆

问题	原因	解决
路径偶尔不是最便宜的	入堆时就当作“已确定”，或找到终点时就停（而不是终点出堆时）	只有出堆时代价才是最终的
结果错误或死循环	地图上有负代价	保证代价 ≥ 1；确实需要时用 Bellman-Ford
代价莫名其妙变成负数	用 INT_MAX 表示未访问，再加上代价时溢出	只对已出堆的格子做加法，或用一个不会溢出的大数
代价是浮点数时路径抖动	浮点比较的舍入误差	代价放大成整数，例如 1.5 → 15
往返代价不对称让人困惑	代价定义在“进入格子”上	这是常见约定；需要对称时，把代价定义在边上
比 BFS 慢很多	代价全为 1 时也在用堆	统一代价的地图直接用 BFS

还能更快吗

Dijkstra 向所有方向均匀扩散，即使终点就在正右方，它也会把左边的格子探索一遍。演示里 expanded 往往接近整张地图的格子数。如果知道终点的大致方向，就可以优先探索朝向终点的格子，这正是下一篇 A* 的思路。

在游戏中的应用

• 策略游戏的移动范围：单位有 10 点行动力，从它出发跑一次 Dijkstra，代价 ≤ 10 的格子就是可以移动到的范围。这比 BFS 版本多考虑了地形。
• 道路网络：城市之间的道路图上，代价是道路长度，导航就是一次 Dijkstra。
• Roguelike 的怪物 AI：Dijkstra 地图让成百上千的怪物共享一次计算。
• 影响力与危险度：以敌方炮塔为源点、代价为距离，得到一张“离危险有多近”的表，供 AI 决策使用。

练习

1. 实现“行动力范围”：给定起点和行动力 N，返回所有总代价 ≤ N 的格子。提示：当出堆的代价超过 N 时就可以停止。
2. 把代价从“进入格子”改为“格子之间的边”，例如上坡代价 3、下坡代价 1。需要修改哪些代码？
3. 用两张 Dijkstra 地图实现一个“怕玩家但想拿宝箱”的怪物：desire = treasureMap - 0.5 × playerMap，每步走向 desire 最小的邻居。
4. 测量本页 dijkstraPath 在 256×256 地图上的耗时，再试试把 costSoFar 等数组改为在多次调用之间复用。

延伸阅读

• Amit Patel，Introduction to the A* Algorithm：BFS、Dijkstra、A* 的统一视角
• Brian Walker，The Incredible Power of Dijkstra Maps：Brogue 作者对 Dijkstra 地图的经典介绍
• Introduction to Algorithms（CLRS）第 24 章：单源最短路径，包含 Dijkstra 与 Bellman-Ford 的证明