图的最短路径怎样求？BFS 和 Dijkstra 有什么区别？

简答

地铁换乘问“从 A 站到 B 站最少坐几站”，每一站算一步，这是边权都相同的最短路径，用 BFS。如果问“最少花多少分钟”，每段路耗时不同，就是带权最短路径，用 Dijkstra。图在代码里通常存成邻接表：每个点对应一个数组，列出它能直接到达的点和边的长度。

BFS 用队列从起点出发一层层往外走：先走到所有距离 1 的点，再走到距离 2 的点。因为是按层推进的，某个点第一次被访问时，走过的步数一定最少，所以 O(V + E) 就能求出所有点的最短步数，V 是点数，E 是边数。

边长不一样时，少走几步不代表路程短，BFS 就不对了。Dijkstra 的做法是：每次从还没确定的点里，挑出当前已知距离最小的那个，它的距离就不会再变小，因为其他路线都得先绕到一个更远的点，边权又不为负，只会更长。确定它以后，用它去更新邻居的距离，这一步叫松弛。用最小堆来挑最小值，复杂度是 O((V + E) log V)。

要注意，Dijkstra 要求边权非负，有负权边时“当前最小就已确定”的推理不成立，要换成 Bellman-Ford。另外用堆实现时，同一个点可能被多次放进堆，取出时要跳过已经过期的记录。

边权相同：BFS

先看 BFS 怎样同时记录距离和“从哪里来”，后者用来还原整条路径。

JavaScript

function shortestPathBFS(graph, start, target) {
  const prev = new Map([[start, null]]);
  const queue = [start];
  let head = 0; // 用下标出队，避免 shift 挪动整个数组
  while (head < queue.length) {
    const node = queue[head++];
    if (node === target) break;
    for (const next of graph[node] ?? []) {
      if (prev.has(next)) continue; // 已经访问过，第一次到达时就是最短
      prev.set(next, node);
      queue.push(next);
    }
  }
  if (!prev.has(target)) return null;
  const path = [];
  for (let node = target; node !== null; node = prev.get(node)) path.push(node);
  return path.reverse();
}

const subway = {
  A: ['B', 'C'],
  B: ['A', 'D'],
  C: ['A', 'D', 'E'],
  D: ['B', 'C', 'F'],
  E: ['C', 'F'],
  F: ['D', 'E'],
  G: [],
};

console.log(shortestPathBFS(subway, 'A', 'F').join('→')); // A→B→D→F
console.log(shortestPathBFS(subway, 'A', 'A').join('→')); // A
console.log(shortestPathBFS(subway, 'A', 'G')); // null

为什么一访问过就跳过，不担心后面有更短的路？BFS 先处理完所有距离为 k 的点，才开始处理距离为 k + 1 的点。一个点第一次被发现时，它的距离就是发现它的那一层加 1，之后再发现它的路线只会在同一层或更深的层，不会更短。

A→C→D→F 和 A→C→E→F 也是 3 步，为什么输出的是经过 B 的那条？A 的邻居里 B 排在前面，B 先入队，所以 D 是从 B 发现的。最短路径有多条时，BFS 返回哪一条取决于邻居的顺序。

二叉树的层序遍历也是 BFS，只是树里不会重复访问节点，不用 prev 判重，见《二叉树怎样层序遍历、求最大深度？》。

边权不同：Dijkstra

下面先写一个最小堆，按距离取出点，再看主循环里的“过期记录”判断。

JavaScript

class MinHeap {
  constructor() {
    this.items = [];
  }
  get size() {
    return this.items.length;
  }
  push(item) {
    const a = this.items;
    a.push(item);
    let i = a.length - 1;
    while (i > 0) {
      const p = (i - 1) >> 1;
      if (a[p][0] <= a[i][0]) break;
      [a[p], a[i]] = [a[i], a[p]];
      i = p;
    }
  }
  pop() {
    const a = this.items;
    const top = a[0];
    const last = a.pop();
    if (a.length > 0) {
      a[0] = last;
      let i = 0;
      while (true) {
        const l = 2 * i + 1;
        const r = l + 1;
        let m = i;
        if (l < a.length && a[l][0] < a[m][0]) m = l;
        if (r < a.length && a[r][0] < a[m][0]) m = r;
        if (m === i) break;
        [a[m], a[i]] = [a[i], a[m]];
        i = m;
      }
    }
    return top;
  }
}

function dijkstra(graph, start) {
  const dist = new Map([[start, 0]]);
  const heap = new MinHeap();
  heap.push([0, start]);
  while (heap.size > 0) {
    const [d, node] = heap.pop();
    if (d > dist.get(node)) continue; // 过期记录：这个点已经用更短的距离处理过
    for (const [next, weight] of graph[node] ?? []) {
      const candidate = d + weight;
      if (candidate < (dist.get(next) ?? Infinity)) {
        dist.set(next, candidate); // 松弛：找到了更短的路线
        heap.push([candidate, next]);
      }
    }
  }
  return dist;
}

const roads = {
  A: [['B', 4], ['C', 1]],
  B: [['D', 1]],
  C: [['B', 2], ['D', 5]],
  D: [['E', 3]],
  E: [],
  F: [['A', 1]],
};

console.log(JSON.stringify(Object.fromEntries(dijkstra(roads, 'A'))));
// {"A":0,"B":3,"C":1,"D":4,"E":7}
console.log(JSON.stringify(Object.fromEntries(dijkstra(roads, 'E')))); // {"E":0}
console.log(dijkstra({ X: [['Y', 0]], Y: [] }, 'X').get('Y')); // 0

A 到 B 为什么是 3 而不是 4？直接走 A→B 长度是 4，但先到 C（1）再到 B（2）只要 3。BFS 只看步数，会选一步就到的 A→B；Dijkstra 先取出距离最小的 C，用它把 B 的距离从 4 松弛成 3。D 也一样，A→C→B→D 是 4，比 A→C→D 的 6 短。

d > dist.get(node) 在过滤什么？B 先以距离 4 进堆，后来又以 3 进堆，堆里同时有两条 B 的记录。距离 3 的那条先被取出并处理；距离 4 的那条之后取出时已经过期，直接跳过。这种写法叫懒删除，因为 JS 没有内置的堆，也没有现成的“减小某个元素的键”操作，多放几条记录再跳过最简单。

F 为什么不在结果里？F 有一条到 A 的边，但从 A 出发没有路能到 F，所以 dist 里没有它。查询时 dist.get('F') 是 undefined，可以按需要当成 Infinity，表示不可达。

复杂度怎么算？每条边最多触发一次成功的松弛，所以堆里最多有 E + 1 条记录，每次进出堆 O(log E)。E 不超过 V²，log E 不超过 2 log V，所以通常写成 O((V + E) log V)。不用堆、每次线性扫描找最小值时是 O(V²)，点很少但边很密时反而更简单。

负权边为什么不行

Dijkstra 的正确性建立在一个推理上：取出的点距离最小，别的路线都要先经过一个距离更大的点，再加上非负的边，只会更长。有负权边时，绕一段远路再走一条负边，可能反而更短，已经“确定”的距离就是错的。

比如 A→B 长 2，A→C 长 3，C→B 长 -2。用 visited 集合标记“已确定”的经典写法，会先确定 B 的距离是 2，之后不再处理 B，可实际上 A→C→B 只要 1。上面的懒删除写法没有 visited，B 被松弛成 1 后会再次进堆、重新处理，这个小例子碰巧算对了；但这样一个点可能被反复处理，O((V + E) log V) 的保证就没了，最坏情况会是指数级。所以有负权边时应当换成 Bellman-Ford：把所有边松弛 V - 1 轮，复杂度 O(V × E)，还能检测负权环。

常见追问

前端哪里会用到最短路径？

地图和导航的路线规划、流程图编辑器里自动连线避开节点、游戏里角色寻路。网格寻路常用 A*，它是 Dijkstra 加上一个“离终点还有多远”的估计值，让搜索优先朝终点方向展开。

边权只有 0 和 1 时有更快的办法吗？

有，叫 0-1 BFS。用双端队列代替堆：走权重 0 的边时把新点放到队头，走权重 1 的边时放到队尾，这样队列始终按距离有序，复杂度是 O(V + E)。