BFS 与最短路径

Dijkstra 最短路径

它就是换了个队列的 BFS

BFS 求最短路的前提是每条边代价相同。 边有权重时那条性质就断了 —— 走 1 条边可能比走 3 条边还贵。

Dijkstra 的做法只改一件事：普通队列换成优先级队列（按「从起点到该节点的已知最短距离」排序）。

BFS 每次弹出「最早入队的」，Dijkstra 每次弹出「当前距离最小的」。 边权全是 1 时，这两者恰好等价 —— BFS 是 Dijkstra 的特例。

function dijkstra(start, n, adj) {
  // dist[i] = 从 start 到 i 的最短距离，未知先设为 Infinity
  const dist = new Array(n).fill(Infinity);
  dist[start] = 0;

  const pq = new MinHeap();            // 见下方实现
  pq.push([0, start]);                 // [距离, 节点]

  while (pq.size > 0) {
    const [d, u] = pq.pop();

    // 🚨 这一行是关键，不能省。见下方「为什么不需要 visited」
    if (d > dist[u]) continue;

    for (const [v, w] of adj[u]) {
      const nd = d + w;
      if (nd < dist[v]) {
        dist[v] = nd;
        pq.push([nd, v]);
      }
    }
  }

  return dist;
}

🚨 为什么没有 visited，而是 if (d > dist[u]) continue

JavaScript 没有内置优先级队列，也没有「降低某个元素优先级」的操作。 所以标准做法是允许同一个节点被多次入队（每次找到更短的路径就再推一次）， 弹出时用 d > dist[u] 把过期的那些跳过。

这叫惰性删除。它比维护 visited 更简单，代价是队列里会有冗余项 —— 但冗余项被弹出时一次判断就丢掉了，总复杂度不变。

⚠️ 省掉这一行会怎样：答案仍然是对的（dist 数组早就更新过了）， 只是每个过期项都会把它的邻居白白再松弛一遍。

实测（200 节点的阶梯图）：带 continue 松弛 594 次，省掉后 675 次 —— 多 14%，不是数量级。所以它属于「该写但不至于致命」的那类， 比 BFS 那条 visited 标记位置轻得多 —— 那一条在网格上会变成组合爆炸（12×12 就膨胀一万八千倍），不是百分之几。

📌 之所以把这个数字放上来，是因为**「不写会怎样」的量级值得知道**： 知道它只是 14%，你就不会在面试时因为漏了这一行而慌。

🚨 负权边：教科书版会给出错误答案

Dijkstra 的正确性建立在一个假设上：

一旦某个节点被弹出，它的距离就是最终值，不会再变小。

依据是「后面的路只会更长」—— 这只在边权非负时成立。 所以教科书版（弹出即定终身，用一个 visited 集合）在负权边上会翻车：

// ⚠️ 这是会出错的版本，对照用
if (seen.has(u)) continue;
seen.add(u);                    // 定终身：以后不再从 u 出发松弛

反例（起点 0）：

0 --1--> A --5--> C
0 --2--> B --(-2)--> A

真实最短 C = 0→B→A→C = 2 + (-2) + 5 = 5。而教科书版：

  1. 弹出 A（距离 1），定终身，松弛出 dist[C] = 6
  2. 弹出 B（距离 2），松弛出 dist[A] = 0 —— A 的距离确实变短了
  3. 但 A 已经定终身，再也不会从它出发松弛一次，dist[C] 永远停在 6

实测：教科书版 C = 6，真值 C = 5。 ⚠️ 它不报错、不死循环，就是安静地给一个错的数。

⭐ 但本篇这一版会算对 —— 而这不值得高兴

上面那份惰性删除的代码没有 seen，所以 A 的距离变短时会重新入队， C 也就跟着被重新松弛。实测它给出 C = 5，是对的。

这不是 Dijkstra 变强了，是它已经不是 Dijkstra 了 —— 允许节点反复入队重算，本质上就是带优先级队列的 Bellman-Ford。代价有两条：

  • 复杂度保证没了。 O((V+E) log V) 的证明依赖「每个节点只出队一次」， 负权边下这个前提不成立，最坏可以退化到指数级。
  • 🚨 遇到负权环会永不终止。 实测在一个含负环的三节点图上跑， 弹出五万次仍在继续，距离被压到 −49997 还在往下掉。 教科书版至少会停下来（虽然答案是错的）。

👉 所以结论不变：看到负权边，别用 Dijkstra —— 不管你写的是哪一版。区别只是「安静地错」还是「安静地不停」。

📌 换成 Bellman-Ford：对所有边松弛 V-1 轮，O(V·E)。慢，但能处理负权， 而且第 V 轮还能变化就说明存在负权环（那时最短路根本不存在，它会告诉你）。 SPFA 是它的队列优化版，平均快很多，最坏仍是 O(V·E)。

优先级队列：得自己写

JavaScript 没有内置的。面试里手写一个二叉堆是常见要求，好在只有二十来行：

class MinHeap {
  constructor() { this.a = []; }
  get size() { return this.a.length; }

  push(item) {
    this.a.push(item);
    let i = this.a.length - 1;
    while (i > 0) {
      const p = (i - 1) >> 1;
      if (this.a[p][0] <= this.a[i][0]) break;
      [this.a[p], this.a[i]] = [this.a[i], this.a[p]];
      i = p;
    }
  }

  pop() {
    const top = this.a[0];
    const last = this.a.pop();
    if (this.a.length > 0) {
      this.a[0] = last;
      let i = 0;
      for (;;) {
        const l = 2 * i + 1, r = l + 1;
        let m = i;
        if (l < this.a.length && this.a[l][0] < this.a[m][0]) m = l;
        if (r < this.a.length && this.a[r][0] < this.a[m][0]) m = r;
        if (m === i) break;
        [this.a[m], this.a[i]] = [this.a[i], this.a[m]];
        i = m;
      }
    }
    return top;
  }
}

🚨 pop() 里那个 if (this.a.length > 0) 不能省。

省掉之后，堆里只剩一个元素时：this.a.pop() 把数组清空， 紧接着 this.a[0] = last 又把它塞了回去 —— 数组长度重新变成 1。 于是 size 永远归不了零，while (pq.size > 0) 变成死循环。

实测：单元素堆 pop 一次后 size 仍是 1，循环跑一千次也不停。

⚠️ 而前面所有操作都完全正常 —— 只有「弹出最后一个」这一步出问题。 所以它在能提前 return 的题里可能永远不触发， 换一道要把堆掏空的题就直接挂起，且没有任何报错。

⭐ 用有序数组代替堆也能跑（push 后 sort），代码短很多， 面试时先说「这里用堆，为了先跑通我先用排序数组代替」是完全可接受的 —— 比在堆的边界上卡十分钟强。

复杂度

O((V + E) log V)。每条边最多让一个元素入堆，每次堆操作 O(log V)。

⭐ 对比一下三者，判据就清楚了：

边权 复杂度 负权
BFS 全部为 1 O(V + E) —
Dijkstra 非负 O((V+E) log V) 不行
Bellman-Ford 任意 O(V·E) 行，还能检测负环

👉 先看边权：全是 1 用 BFS，有正权重用 Dijkstra，出现负数才上 Bellman-Ford。 别默认上 Dijkstra —— 边权全 1 时它只是一个慢了 log V 倍的 BFS。

📌 以上都是单源：给一个起点，求到各点的距离。 如果题目要的是任意两点之间的距离，或者点数不多（≲ 400）而边很密， 看 Floyd 多源最短路 —— 三重循环写完，顺带支持负权，还能一行检测负环。 实测在稠密图上它比跑 V 次 Dijkstra 快 7 倍。

练习

勾选记录做过哪些，0 / 5 道。进度只存在这台设备的浏览器里；同一道题在别篇勾过，这里也会显示已做。

⚖️ 这里只给题号、官方标题和链接，不复述题面 —— 平台的题面文字有版权。 「这题考什么」写的是它对应本篇的哪个点，那部分是本站自己的内容。