Dijkstra 最短路

图算法 · 单源最短路径

什么是最短路

带权图里，从一个起点到各个点的「最短总距离」是多少、怎么走？逐条路径去试不现实。Dijkstra 给了高效解法——前提是边权非负。

Dijkstra 怎么做

维护一张「源到各点的当前最短距离」表（源点为 0，其余为 ∞）。然后反复做两步：①取出还没定下来、当前距离最小的点，把它「定下来」；②用它去松弛（relax）邻边——如果「经它中转」到某个邻居更短，就更新那个邻居的距离。每个点被定下来时，它的距离就是最终最短距离。

下面固定一张 6 个点的带权有向图（源 A）。点「下一步」逐步看它怎么取当前最近点（琥珀高亮）、确定它（变绿）、松弛邻边（黄边+ 节点旁距离徽标更新）——特别留意 B、D、E、F 的距离会被更短的路径反复降低（先到的不一定最短）；走到底会点亮整棵最短路树（绿边）。右侧代码随每一步同步高亮。

源 A 距离置 0，其余置 ∞

1function dijkstra(adj: [number, number][][], source: number, n: number): number[] {
const dist = Array(n).fill(Infinity);
dist[source] = 0;
const done = Array(n).fill(false);
for (let k = 0; k < n; k++) {
  let u = -1;
  for (let i = 0; i < n; i++)
    if (!done[i] && dist[i] < Infinity && (u < 0 || dist[i] < dist[u])) u = i;
  if (u < 0) break;
  done[u] = true;
  for (const [v, w] of adj[u]) {
    if (dist[u] + w < dist[v]) {
      dist[v] = dist[u] + w;
    }
  }
}
return dist;
18}

u（当前点）-

已确定-

dist[A]0

dist[B]∞

dist[C]∞

dist[D]∞

dist[E]∞

dist[F]∞

1 / 32

为什么「贪心地取当前最近点」是对的？因为边权非负，一个已经定下来的点，它的距离不可能再被后面更小——后面的路只会更长。用二叉堆做优先队列，复杂度约 O((V + E) log V)。注意它不能处理负权边（那要用 Bellman-Ford）。

Dijkstra 在哪里用

地图 / 导航：求两地最短路线。
网络路由：如 OSPF 协议按链路开销选路。
任何「非负权图上的单源最短路」。

它是图算法这条线的开篇——后面还有 Bellman-Ford（带负权）、Floyd（多源最短路）、最小生成树、拓扑排序等。想先复习图本身怎么存、怎么遍历，可回看 数据结构 · 图。

算法可视化

Dijkstra 最短路

什么是最短路

Dijkstra 怎么做

Dijkstra 在哪里用