先还原一次外卖配送的线上事故。调度服务要给骑手算最短路线,图是城市路网,每条边的权重是历史平均通行时间。实现用的却是 BFS(广度优先搜索,按边数一层层向外扩展的遍历方式),理由是「BFS 天然就是最短路」。它数的是经过几个路口,不是花几分钟。系统于是把一条四路口、二十七分钟的路排在第一位,把一条六路口、十四分钟的路排在后面。骑手按推荐走,当天超时率涨了一截。

复盘时最扎心的一句话是:代码没有崩溃,它只是回答了一个不一样的问题。BFS 回答「最少几条边」,业务问「最少多少时间」。只有每条边代价相同时,这两件事才等价。路网里红绿灯、高架、晚高峰把每条边的耗时拉开几倍,等权假设一破,答案就错。

这篇把 BFS 换成 Dijkstra(迪杰斯特拉,处理非负权图的最短路径算法),并讲清它为什么成立。重点不是背 O((V+E) log V),而是理解一条不变量:从优先队列取出的点,距离已经不会再被改小。负权正是从这里把算法推翻。

现场:跳数最少的路线,时间反而最长

把事故图缩小到四个点。A 是商家,D 是顾客,B 和 C 是路口。A 到 B 是 1 分钟,A 到 C 是 4 分钟,B 到 C 是 1 分钟,B 到 D 是 5 分钟,C 到 D 是 1 分钟。每条边都有一个非负权重。

BFS 从 A 出发按边数分层:A 第 0 层,B 和 C 都有直达边,都在第 1 层,D 走 A-B-D 或 A-C-D 都是两条边,所以第 2 层。按跳数排序,A 到 C 是一跳,A 到 D 是两跳,系统于是认为 A-C-D 优于 A-B-C-D。

真实时间是另一回事。A 到 C 直达 4 分钟,绕 A-B-C 只要 1 加 1 等于 2 分钟;A 到 D 走 A-C-D 是 5 分钟,走 A-B-C-D 只要 3 分钟。跳数少的更慢,跳数多的更快。这不是 BFS 的 bug,而是它被问了一个不属于它的问题。

只有业务真的只关心经过几个路口时,BFS 才够用。一旦模型里出现时间、距离、费用这类可累加的量,就必须把权重放进算法;算完跳数再乘平均值,等于把每条边的差异抹平,误差会被路径长度放大。

带权图:把「几步」换成「几分钟」

图由顶点和边组成。顶点是要考虑的实体,这里是商家、路口和顾客;边表示两个顶点之间有一条可以直接走的路。带权图给每条边记一个数字,叫权重,这里是通行时间。路径长度不是边的条数,而是路径上所有边权的和。

边还有方向。单向街道、只能单向走的匝道,都要建成有向边:从 u 指向 v,只允许从 u 走到 v。双向通行则在两个方向各建一条边;本文示例都是有向图。

程序里常用邻接表:每个顶点对应一个对象,键是邻居,值是权重。下面是示例图,读法是「A 到 B 权重 1,A 到 C 权重 4」,D 没有出边所以是空对象。

const graph = {
  A: { B: 1, C: 4 },
  B: { C: 1, D: 5 },
  C: { D: 1 },
  D: {},
};

算法还要一个距离数组 dist,记录目前已知的从起点到每个点的最小代价。一开始除起点为 0 外,其余全是无穷大。无穷大不是数字,是「还没发现任何走法」的标记,用 Infinity 表示,有限值加它仍是无穷,方便比较。

BFS 的排序依据

按已走过的边数排序,先访问离起点边数少的点。每条边代价相同时它给出的就是最短路,复杂度 O(V+E)。边权一旦不等,它给的只是跳数最少。

Dijkstra 的排序依据

按目前累计代价排序,每次取代价最小的未定点。要求所有边权非负,用二叉堆是 O((V+E) log V),给出的是真正的最小代价。

两者的差别不在遍历方式,而在谁先被拿出来处理。BFS 用先进先出,默认先发现的层更优;Dijkstra 用优先队列,永远先处理当前最便宜的点。这个顺序选择正是不变量的来源。

松弛:发现更短的走法就更新距离

松弛(relaxation)这个词听起来抽象,做的事情只有一件:手里已经有一条到 v 的走法,代价记为 dist[v];现在从 u 出发多走一条边也能到 v,代价是 dist[u] 加这条边的权重;如果后者更小,就把 dist[v] 改成后者。没有更小,就什么都不做。

把它想成导航软件刷新预计到达时间:先显示三十分钟,发现快速路改成二十五分钟,遇到事故又改成四十分钟。每次根据新信息修正估计,就是一次松弛。算法的工作就是把所有边按这个规则检查一遍,直到没有能改小的。

程序里写成一句判断。注意这里的 dist[v] 只是上界,意思是「现在知道的最好走法」,不代表最终答案。把暂定和最终混为一谈,是后面所有误解的起点。

if (dist[u] + w < dist[v]) {
  dist[v] = dist[u] + w;
}

整个流程可以画成一条循环:初始化距离,把起点放进堆;每次取出当前代价最小的点;用这个点松弛它的所有出边;把距离变小的邻居重新放回堆;重复到堆空。堆空时,所有从起点可达的点都应该已经有了最终距离。

Dijkstra 的一轮循环
初始化:起点 0,其余无穷
取堆顶:当前代价最小的未定点
松弛:更新它所有出边的终点
回填:变小的点重新入堆

已确定集合:为什么取出来的点可以定案

算法维护一个集合 S,里面放「距离已经最终确定」的点。每次从堆里取出距离最小的点 u,就把它放进 S,并且以后不再修改它的距离。这个做法看起来有点武断:凭什么现在最小,以后就不会被别的走法反超?答案依赖两个条件,缺一不可。

先看直观的论证。假设 u 是堆里距离最小的点,距离为 d。如果存在另一条更短路径到 u,它一定在某个位置第一次离开 S,进入未确定区域。设离开前最后一个在 S 里的点是 x,下一个点是 y。x 的距离已在出堆时定案,路径到 x 的那段不会比 dist[x] 更短;而 y 的当前距离不会小于 d,否则堆顶就不是 u。于是这条「更短路径」到 y 时至少是 d,再经过非负边到 u 只会更大,不可能比 d 小。

这段论证用了两个条件:堆顶是当前最小;边权非负。两者成立时,u 确实可以定案。于是每个点只需取出、松弛一次,算法在有限步内结束。

只要有一条边权重为负,第二个条件就破了:从 y 到 u 的那一步可能把总代价拉低,「更短路径」可以在 u 定案之后才出现。这就是负权问题的全部根源。

堆优化与懒删除

每次取当前代价最小的点,需要一个总能弹出最小元素的容器,叫优先队列,底层常用二叉堆,插入和弹出都是 O(log n)。JavaScript 没有内置堆,本文手写一个小版本,只支持放入和弹出最小项。

手写细节不是重点,重点是懒删除。同一个点可能被多次放松,堆里会留下好几条记录:C 先以 4 入堆,后来以 2 又入堆一次。旧的 4 不主动删,等它被弹出时发现 C 已在 S 里,直接跳过。删除推迟到看见它的那一刻。

完整代码如下。堆里存「距离, 顶点」二元组;done 就是 S;弹出时已定案就跳过;松弛时也跳过已定案的点,保证 S 里的距离不被改写。

class MinHeap {
  constructor() { this.a = []; }
  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() {
    if (!this.a.length) return null;
    const top = this.a[0];
    const last = this.a.pop();
    if (this.a.length) {
      this.a[0] = last;
      let i = 0;
      while (true) {
        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[i], this.a[m]] = [this.a[m], this.a[i]];
        i = m;
      }
    }
    return top;
  }
  get size() { return this.a.length; }
}

function dijkstra(graph, start) {
  const dist = {};
  for (const v of Object.keys(graph)) dist[v] = Infinity;
  dist[start] = 0;
  const heap = new MinHeap();
  heap.push([0, start]);
  const done = new Set();
  while (heap.size) {
    const [d, u] = heap.pop();
    if (done.has(u)) continue;
    done.add(u);
    for (const [v, w] of Object.entries(graph[u])) {
      if (done.has(v)) continue;
      if (dist[u] + w < dist[v]) {
        dist[v] = dist[u] + w;
        heap.push([dist[v], v]);
      }
    }
  }
  return dist;
}

用本文开头的图跑一遍,起点是 A:

console.log(JSON.stringify(dijkstra(graph, 'A')));
// 输出:{"A":0,"B":1,"C":2,"D":3}

把过程走一遍。A 出堆,B 变成 1、C 变成 4;B 出堆,C 改成 2、D 变成 6;C 的旧记录 4 还在堆里,但 C 的新记录 2 先弹出并定案,随后把 D 改成 3;D 出堆。旧的 C 等于 4 和旧的 D 等于 6 后来被弹出,都因已定案跳过。最终四个距离是 0、1、2、3。

复杂度这样算:每个点只出堆定案一次,每条边只从它的起点被松弛一次,总共扫描 O(E) 条边;每次成功松弛可能入堆一次,总入堆不超过 E;每次 O(log V),合起来 O((V+E) log V)。空间是 O(V+E) 加上堆里最多 O(E) 条记录。比 BFS 多一个对数,换来能处理不同权重。

稠密图另有写法:不用堆,每轮线性扫描未定点找最小值,复杂度 O(V 的平方)。接近完全图时平方级别反而更省。选哪种要看边数相对顶点数的量级,而不是死记堆优化。

负权:不变量从哪里断掉

现在把一条边改成负数。还是四个点,但去掉 D,只留 A、B、C:A 到 B 直连代价 2,A 到 C 代价 5,C 到 B 代价负 4。负权在现实里可能表示补贴、返程顺路带来的负成本,也可能只是建模时把符号写错了。先不管语义,只看算法怎么走。

A 出堆,B 等于 2,C 等于 5,都入堆。堆顶是 B 的 2,B 出堆定案;B 没有出边。接着 C 等于 5 出堆,松弛 C 到 B:5 加负 4 等于 1,比 B 现在的 2 更小。但 B 已经在 S 里,代码直接跳过,距离保持 2。算法结束,输出 B 等于 2。

const graph2 = {
  A: { B: 2, C: 5 },
  B: {},
  C: { B: -4 },
};
console.log(JSON.stringify(dijkstra(graph2, 'A')));
// 输出:{"A":0,"B":2,"C":5}

真实的最短路是 A 到 C 再到 B,2 加 5 再减 4 等于 1。算法给出的 2 是错的,而且没有任何报错,只是安静地给了一个偏大的数。这正是负权最危险的地方:错误以「看起来合理」的距离混进业务结果。

再看一个更能说明后果的版本。给 B 加一条到 D、权重 1 的边。Dijkstra 会在 B 定案时把 D 定成 3;之后 C 发现 B 其实可以是 1,但 B 的出边已经处理过,D 不会再改。真实最短路是 2。

const graph3 = {
  A: { B: 2, C: 5 },
  B: { D: 1 },
  C: { B: -4 },
  D: {},
};
console.log(JSON.stringify(dijkstra(graph3, 'A')));
// 输出:{"A":0,"B":2,"C":5,"D":3}

机制上说,负权不是让「堆排序」变慢,而是让「堆顶最小」和「最终最小」不再等价。非负权时,任何绕远的走法只会让代价变大,所以当前最小的点不可能被后来的路径反超;有负权时,一条现在看起来更贵的路,可能因为后面有一段负边,最终反而更便宜。已确定集合的前提被抽掉了,定案就成了误判。

如果负权边还构成一个环,问题会再升一级。绕着环走一圈总代价是负的,每多绕一圈距离就更小,最短路径根本不存在,距离会趋向负无穷。这时算法不该返回任何数字,而应该明确报告「存在可达的负环」。Dijkstra 连单个负权边都处理不了,负环自然更不在它的能力范围内。

负权怎么办:Bellman-Ford 与负环检测

Bellman-Ford(贝尔曼-福特)换了一个思路:不猜哪个点已经定案,而是把所有边反复松弛。道理是,如果没有负环,一条最短路径一定可以取成不绕圈的简单路径,最多包含 V 减 1 条边。所以做 V 减 1 轮,每轮把所有边扫一遍,距离一定收敛到最终值。

代码比 Dijkstra 短,也不需要堆。外层跑 V 减 1 轮,内层遍历所有边做松弛。跑完后再扫一遍:如果还能把某个距离改小,说明存在从起点可达的负环,因为正常情况下 V 减 1 轮之后不该再有改进。

function bellmanFord(graph, start) {
  const dist = {};
  for (const v of Object.keys(graph)) dist[v] = Infinity;
  dist[start] = 0;
  const n = Object.keys(graph).length;
  for (let round = 0; round < n - 1; round++) {
    for (const u of Object.keys(graph)) {
      if (dist[u] === Infinity) continue;
      for (const [v, w] of Object.entries(graph[u])) {
        if (dist[u] + w < dist[v]) dist[v] = dist[u] + w;
      }
    }
  }
  for (const u of Object.keys(graph)) {
    if (dist[u] === Infinity) continue;
    for (const [v, w] of Object.entries(graph[u])) {
      if (dist[u] + w < dist[v]) return { dist, hasCycle: true };
    }
  }
  return { dist, hasCycle: false };
}

用前面那个负权图跑,B 会被正确改成 1;再构造一个负环:A 到 B 是 1,B 到 C 是负 2,C 到 B 是负 1,B 和 C 之间绕一圈总代价是负 3。检测结果为存在负环,距离数字继续变小,已经没有实际意义。

console.log(JSON.stringify(bellmanFord(graph2, 'A')));
// 输出:{"dist":{"A":0,"B":1,"C":5},"hasCycle":false}

console.log(JSON.stringify(bellmanFord(
  { A: { B: 1 }, B: { C: -2 }, C: { B: -1 } }, 'A'
)));
// 输出:{"dist":{"A":0,"B":-5,"C":-4},"hasCycle":true}

复杂度 O(V 乘 E),比 Dijkstra 慢一个量级,但适用范围更宽。工程上常见变体 SPFA 用队列优化,只把距离刚被改小的点入队,平均快很多;最坏仍是 O(V 乘 E),刻意构造的图会退化,不能当成永远更快。

还有一个实用特例:如果图是有向无环图(DAG,拓扑排序那一篇会详细讲),按拓扑序处理每个点一次,所有能到它的点都已处理完,松弛一遍就得到最终距离,复杂度 O(V+E)。所以负权最短路并不总是很贵,贵的是有环的任意图。

现象、真实原因与第一步排查

最短路算错时,症状往往不在算法函数里,而在数据和建模上。下面这些情况出现频率很高,顺序也大致对应从「模型错了」到「实现错了」的排查路径。

现象真实原因第一步查什么
推荐路线时间明显偏长用跳数或平均耗时,没有累加每条边权距离数组是否按边权求和
部分点距离偏大且图里有负边负权破坏了定案不变量,已出堆的点不再更新权重是否有负数,负环是否存在
结果里一堆 Infinity不可达,或边方向建反了从起点做一次可达性遍历
两次运行路线顺序不同距离相同的点出堆顺序不稳定是否需要固定的 tie-break
堆条目远多于顶点懒删除保留了旧记录,或重复入堆是否用 done 跳过已定案的点
大图跑到一半内存飙升邻接表、重复边和堆记录都占内存实际边数与重复边
浮点权重比较忽好忽坏浮点累加误差是否改用整数权重
单向路当成双向,路线短得不合理建图时两个方向都加了边边是否只按真实方向建立
负环时只输出异常小的数没做第 V 轮检测收敛后是否再扫一遍边

表里最容易误判的是第一行和第五行。第一行看起来像路网数据过期,其实是算法在回答另一个问题;第五行看起来像堆的实现有 bug,其实懒删除本来就会留下旧条目,关键是有没有在弹出时跳过。判断最短路问题,先问距离按什么累加,再问取出的点凭什么定案,最后才看代码。

边界与代价

Dijkstra 最硬的边界是所有边权非负。这不是实现细节,而是正确性前提。零权可以,因为不改变「不会更小」的结论;负数不行。业务里确实有负数时,要换 Bellman-Ford,或者先转化问题;随便给所有边加常数会改变路径比较,不能乱做。

它算的是单源最短路:一个起点到所有其他点。要任意两点距离,可以对每个点跑一次,或用 Floyd 一类全源算法。稀疏图上跑 V 次 Dijkstra 通常是 O(V 乘 (V+E) log V),稠密图是 O(V 的立方),看规模选。

内存也要算。邻接表每条边一个对象,堆里最多 E 条记录,大图开销不小。路径不会自动保存,要输出「怎么走」得额外维护 prev 数组,松弛成功时记下前驱,最后从终点倒推。多 O(V) 空间,很容易忘。

还有确定性的代价。距离相同的点谁先出堆,取决于堆规则和插入顺序,不同运行可能给出不同路线,虽然总长度一样。路线要进缓存或做对比测试时,得定一个 tie-break 规则,比如距离相同时按顶点编号排。

适用范围:边权非负、规模中等、需要单源距离的图。A 星在已知终点且有启发函数时更快,双向搜索能少扩展点,动态图要增量算法或重跑。它不是唯一答案,只是非负权这张牌桌上最稳的一个。

当天能做的练习

  1. 把图和代码跑一遍,打印每次出堆的顶点与距离,标出哪几次是懒删除跳过的旧记录,确认输出为 A 0、B 1、C 2、D 3。
  2. 在示例图上加点 E,A 到 E 是 10,D 到 E 是 1,手算再运行,确认 E 等于 4;再把 D 到 E 改成负 5,观察输出并解释哪一步定案错了。
  3. 给算法加 prev 数组,松弛成功时记前驱,最后从 D 倒推完整路线;再加一条等长的另一条路线,观察输出是否稳定,设计一个 tie-break 规则。
  4. 构造一个可达负环的图和一个负环不可达的图,分别跑 Bellman-Ford,确认前者 hasCycle 为 true、后者为 false,并说明「可达」为什么重要。
  5. 把示例图改成有向无环图,按拓扑序只松弛一遍,和 Bellman-Ford 对比;记录顶点顺序和两种算法各扫了多少次边。
环境说明:本文代码用 Node.js 24 在本机实际运行,文中所有输出与运行结果一致。不同语言的堆实现和浮点行为会改变常数与末位精度,但松弛规则、定案不变量和负权失效的原因与语言无关。

小结与下一篇

三句话收一下:带权图里路径代价是边权之和,BFS 数的是边数,只有等权时才等价;Dijkstra 靠「取堆顶最小、边权非负」保证取出的点已定案,堆优化和懒删除只是把它做快;负权让后来的走法反超已定案的点,所以负权图要换 Bellman-Ford,负环只能检测、不能求值。

下一篇进入拓扑排序。Dijkstra 处理带权最短路径,需要优先队列反复比较;但有一类图连权重都不需要,只要求「谁必须在谁前面」,按顺序扫一遍就能得到结果,那就是有向无环图。它的排队规则、判环方式与本文的负环检测相通,也补上了「DAG 上负权最短路一遍扫完」这个特例。