【算法图解】最短路径：Dijkstra 算法

BFS 能解决无权图最短路径。

那如果边有权重呢？

道路长度不同
成本不同
延迟不同

只要权重都是非负数，Dijkstra 就是你最常用的答案。

这篇文章让你搞清楚：

它的核心直觉是什么
为什么每次“定点”是安全的
工程实现怎么写（优先队列）
哪些情况不能用（负权边）

1. 问题定义

给定一个带权图 $G=(V,E)$，权重 $w(u,v) \ge 0$。

求从起点 $s$ 到所有点的最短距离 $distv$。

2. Dijkstra 的核心直觉：每次确定一个“当前最近点”

你可以把它想成：

你从起点出发扩散
但扩散速度不是“按层”（那是 BFS）
而是“按当前已知距离最小”

算法维护：

dist[v]：目前已知的最短距离（上界）
一个优先队列：按 dist 最小弹出节点

每次弹出一个节点 u：

这意味着在所有未确定的点里，u 是目前最近
在非负权条件下，它的距离可以“定格”（不会再被更短路径更新）

这就是正确性的关键。

3. 为什么“定格”是对的？（非负权是关键）

反证直觉：

假设 u 被弹出时 dist[u] 不是最短
那存在一条更短路径到 u
这条路径最后一步从某个点 x 到 u
因为边权非负，到达 x 的距离一定 <= 到达 u 的距离

但优先队列总会先弹出距离更小的点，矛盾。

所以：

非负权保证了“从更远的点绕回来变得更近”不可能发生。

一旦出现负权边，这个性质就崩了。

4. 实现：邻接表 + 最小堆（优先队列）

JS 没有内置堆，这里给一个最小可用的二叉堆实现（够面试/够用）。

4.1 最小堆

class MinHeap {
  constructor() {
    this.a = []
  }
  size() { return this.a.length }
  push(item) {
    this.a.push(item)
    this._up(this.a.length - 1)
  }
  pop() {
    if (this.a.length === 0) return null
    const top = this.a[0]
    const last = this.a.pop()
    if (this.a.length) {
      this.a[0] = last
      this._down(0)
    }
    return top
  }
  _up(i) {
    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
    }
  }
  _down(i) {
    const n = this.a.length
    while (true) {
      let m = i
      const l = i * 2 + 1
      const r = l + 1
      if (l < n && this.a[l][0] < this.a[m][0]) m = l
      if (r < n && 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
    }
  }
}

堆里存 [dist, node]。

4.2 Dijkstra

图表示：

const graph = {
  A: [['B', 2], ['C', 5]],
  B: [['C', 1], ['D', 4]],
  C: [['D', 1]],
  D: [],
}

算法：

function dijkstra(graph, start) {
  const dist = new Map()
  const prev = new Map()
  const heap = new MinHeap()

  dist.set(start, 0)
  heap.push([0, start])

  while (heap.size()) {
    const [d, u] = heap.pop()
    if (d !== dist.get(u)) continue // 丢弃过期条目

    for (const [v, w] of graph[u] ?? []) {
      const nd = d + w
      const cur = dist.get(v)
      if (cur == null || nd < cur) {
        dist.set(v, nd)
        prev.set(v, u)
        heap.push([nd, v])
      }
    }
  }

  return { dist, prev }
}