当前目录
← Back

Dijkstra 最短路径算法

Dijkstra 最短路径算法

核心结论

Dijkstra 算法用于求解边权非负的加权图中的单源最短路径。它采用贪心策略：每次从尚未确定最短距离的顶点中，选择当前距离估计最小的顶点，并将该距离永久确定。

目录

1. 问题定义

给定一个加权图：

G=(V,E)G=(V,E)

其中：

  • VV 是顶点集合；

  • EE 是边集合；

  • w(u,v)w(u,v) 是边 (u,v) 的权重；

  • s∈Vs\in V 是指定源点。

Dijkstra 算法需要求出源点 ss 到每个顶点 v 的最短路径距离：

δ(s,v)=min⁡p:s⇝vw(p)\delta(s,v)=\min_{p:s\rightsquigarrow v}w(p)

其中，路径 p 的权重等于路径上所有边权之和。

单源与所有点对

Dijkstra 本身解决的是单源最短路径问题。若要求所有点对最短路径，可以依次将每个顶点作为源点运行一次 Dijkstra。

2. 基本思想

Dijkstra 算法维护两个核心对象：

  1. dist[v]：当前已知的从源点 source 到顶点 v 的最短距离估计；

  2. 已确定集合 S：其中顶点的最短距离已经永久确定。

算法重复执行以下贪心步骤：

  1. 在所有尚未确定的顶点中，选择 dist 最小的顶点 u；

  2. 将 u 加入已确定集合 S；

  3. 使用 u 更新其所有邻接顶点的距离估计；

  4. 直到所有可达顶点均被确定。

直观理解

可以把 dist[v] 理解为源点向外扩张时，到达顶点 v 的当前最低成本。由于边权非负，当前成本最小的未确定顶点不可能再通过其他尚未处理的顶点获得更短路径，因此可以立即确定。

3. 需要问题具有的性质

3.1 边权必须非负

Dijkstra 正确运行的关键条件是：

∀(u,v)∈E,w(u,v)≥0\forall (u,v)\in E,\quad w(u,v)\ge 0

允许存在权重为 0 的边，但不能存在负权边。

负权边会破坏贪心选择

Dijkstra 一旦确定某个顶点的距离，之后不会重新修改该顶点。若图中存在负权边，一个已经确定的顶点可能通过后续路径得到更短距离，从而使算法产生错误结果。

3.2 问题具有最优子结构

最短路径具有如下性质：

一条最短路径的任意子路径，也必须是对应两个端点之间的最短路径。

否则，可以用更短的子路径替换原子路径，从而得到一条更短的完整路径，与原路径最短矛盾。

3.3 图可以是有向图或无向图

  • 有向图：按边的方向进行松弛；

  • 无向图：通常将每条无向边 (u,v,w) 存储为两条有向边：

(u,v,w),(v,u,w)(u,v,w),\quad(v,u,w)

3.4 图不要求连通

若某个顶点无法从源点到达，则最终：

dist[v]=∞\text{dist}[v]=\infty

4. 核心操作：松弛

对于边 (u,v)，若经过 u 到达 v 比当前记录的路径更短，则更新 dist[v]：

dist[v]=min⁡(dist[v], dist[u]+w(u,v))\text{dist}[v] =\min\left(\text{dist}[v],\ \text{dist}[u]+w(u,v)\right)

对应判断为：

if dist[u] + weight < dist[v]:  
    dist[v] = dist[u] + weight  
    parent[v] = u

其中：

  • dist[v] 记录当前最短距离估计；

  • parent[v] 记录当前最短路径中顶点 v 的前驱；

  • parent 数组可用于恢复具体路径。

松弛的含义

松弛并不保证一次就得到最终最短距离。它只是利用一条边检查能否改进当前答案。Dijkstra 通过按距离从小到大的顺序处理顶点，使这些局部改进最终收敛到全局最短路径。

5. 具体过程

设图有 n 个顶点，程序内部使用 0-based 下标：

V={0,1,…,n−1}V=\{0,1,\dots,n-1\}

5.1 初始化

对所有顶点设置：

dist[v]=∞\text{dist}[v]=\infty

源点距离设为：

dist[source]=0\text{dist}[\text{source}]=0

前驱数组初始化为：

parent[v]=−1\text{parent}[v]=-1

将 (0, source) 加入最小优先队列。

5.2 选择当前最近顶点

从最小优先队列中取出距离最小的记录：

(current_dist, u) = extract_min(priority_queue)

此时，若该记录不是顶点 u 的最新距离，则跳过它：

if current_dist != dist[u]:  
    continue

这是使用“重复入堆”代替 DECREASE-KEY 时的过期记录检查。

5.3 松弛邻接边

遍历 u 的每个邻接顶点 v：

new_dist = dist[u] + weight

若：

new_dist<dist[v]\text{new\_dist}<\text{dist}[v]

则更新 dist[v]、parent[v]，并把新的 (dist[v], v) 加入优先队列。

5.4 终止

当最小优先队列为空时：

  • 所有从源点可达的顶点均已得到最短距离；

  • 不可达顶点的距离仍为 ∞\infty。

不变量

每次从优先队列取出的、未过期的最小距离顶点 u，其 dist[u] 已经等于真正的最短路径距离 δ(source,u)\delta(source,u)。

6. 伪代码

6.1 邻接表 + 最小堆

DIJKSTRA(adj, n, source):  
    dist   <- array of size n, initialized to infinity  
    parent <- array of size n, initialized to -1  
​  
    dist[source] <- 0  
​  
    pq <- empty min-priority-queue  
    INSERT(pq, (0, source))  
​  
    while pq is not empty:  
        (current_dist, u) <- EXTRACT-MIN(pq)  
​  
        if current_dist != dist[u]:  
            continue  
​  
        for each (v, weight) in adj[u]:  
            new_dist <- dist[u] + weight  
​  
            if new_dist < dist[v]:  
                dist[v]   <- new_dist  
                parent[v] <- u  
                INSERT(pq, (dist[v], v))  
​  
    return dist, parent

6.2 路径恢复

RESTORE_PATH(parent, source, target):  
    if source != target and parent[target] = -1:  
        return empty path  
​  
    path <- empty list  
    current <- target  
​  
    while current != -1:  
        APPEND(path, current)  
​  
        if current = source:  
            break  
​  
        current <- parent[current]  
​  
    REVERSE(path)  
    return path

7. 正确性要点

Dijkstra 正确性的关键是证明：

每次选择当前 dist 最小的未确定顶点 u 时，dist[u] 已经是源点到 u 的真实最短距离。

设 u 是当前被选中的顶点。反设还存在一条更短路径从源点到 u。

沿这条更短路径，从源点出发，设 y 是第一个尚未确定的顶点，x 是其前一个已经确定的顶点。由于 x 已被处理，边 (x,y) 已经进行过松弛，因此：

dist[y]≤δ(source,y)\text{dist}[y]\le \delta(source,y)

又因为后续边权均非负：

δ(source,y)≤δ(source,u)\delta(source,y)\le \delta(source,u)

所以：

dist[y]≤δ(source,u)<dist[u]\text{dist}[y]\le \delta(source,u)<\text{dist}[u]

这与 u 是当前 dist 最小的未确定顶点矛盾。因此：

dist[u]=δ(source,u)\text{dist}[u]=\delta(source,u)

非负边权的作用

上述证明依赖“从 y 继续走到 u 不会使路径长度减小”。这正是边权非负条件的核心作用。

8. 时空间复杂度

设：

  • ∣V∣|V| 为顶点数；

  • ∣E∣|E| 为边数。

8.1 邻接矩阵 + 顺序查找最小值

每轮通过线性扫描选择最小距离顶点，共进行 ∣V∣|V| 轮：

T(∣V∣,∣E∣)=O(∣V∣2)T(|V|,|E|)=O(|V|^2)

空间复杂度：

O(∣V∣2)O(|V|^2)

该实现适合稠密图或教学演示。

8.2 邻接表 + 二叉最小堆

  • 每个顶点和边会被处理；

  • 入堆、出堆操作的代价为 O(log⁡∣V∣)O(\log |V|)。

常写为：

O((∣V∣+∣E∣)log⁡∣V∣)O((|V|+|E|)\log |V|)

对于连通图，|E|$$\ge ∣V∣|V|-1，可以简写为：

O(∣E∣log⁡∣V∣)O(|E|\log |V|)

空间复杂度：

O(∣V∣+∣E∣)O(|V|+|E|)

若采用允许重复入堆的实现，堆中可能存在过期记录，最坏空间可写得更精确为：

O(∣V∣+∣E∣)O(|V|+|E|)

8.3 Fibonacci 堆

理论上可以达到：

O(∣E∣+∣V∣log⁡∣V∣)O(|E|+|V|\log |V|)

但实现复杂，工程中通常使用二叉堆。

8.4 复杂度总结

图表示与优先队列时间复杂度空间复杂度适用场景
邻接矩阵 + 顺序查找O(∥V∥2)O(\|V\|^2)O(∥V∥2)O(\|V\|^2)稠密图、教学实现
邻接表 + 二叉堆O((∥V∥+∥E∥)log⁡∥V∥)O((\|V\|+\|E\|)\log\|V\|)O(∥V∥+∥E∥)O(\|V\|+\|E\|)稀疏图、常用实现
邻接表 + Fibonacci 堆O(∥E∥+∥V∥log⁡∥V∥)O(\|E\|+\|V\|\log\|V\|)O(∥V∥+∥E∥)O(\|V\|+\|E\|)理论分析

9. 典型例子

9.1 图结构

以下为一个无向加权图，源点为顶点 0：

对应邻接关系来自下列无向边：

(0, 1, 10)  
(0, 3, 30)  
(0, 4, 45)  
(1, 2, 50)  
(1, 4, 40)  
(1, 5, 25)  
(2, 4, 35)  
(2, 5, 15)  
(3, 5, 20)  
(4, 5, 55)

9.2 初始化

源点为 0：

dist=[0,∞,∞,∞,∞,∞]\text{dist}=[0,\infty,\infty,\infty,\infty,\infty]

9.3 执行过程

步骤当前确定顶点松弛后的 dist[0..5]主要更新
0—[0,∞\infty,∞\infty,∞\infty,∞\infty,∞\infty]初始化
10[0,10,∞\infty,30,45,∞\infty]更新 1、3、4
21[0,10,60,30,45,35]更新 2、5
33[0,10,60,30,45,35]经 3 到 5 为 50，不更新
45[0,10,50,30,45,35]经 5 到 2：35+15=50
54[0,10,50,30,45,35]无更优路径
62[0,10,50,30,45,35]算法结束

最终最短距离为：

[0,10,50,30,45,35]\boxed{[0,10,50,30,45,35]}

9.4 最短路径结果

目标顶点最短距离一条最短路径
000
1100→10\to1
2500→1→5→20\to1\to5\to2
3300→30\to3
4450→40\to4
5350→1→50\to1\to5

容易忽略的路径

从 0 到 2 的直接候选路径 0 → 1 → 2 长度为 10+50=60，但经过顶点 5 的路径 0 → 1 → 5 → 2 长度为 10+25+15=50，因此后者更短。

10. 路径恢复

仅有 dist 数组只能得到最短距离，不能直接知道完整路径。因此在每次成功松弛时记录：

parent[v] = u

例如，源点为 0 时可能得到：

parent = [-1, 0, 5, 0, 0, 1]

恢复从 0 到 2 的路径：

2 <- 5 <- 1 <- 0

逆序后得到：

0→1→5→20\to1\to5\to2

多条最短路径

若存在多条长度相同的最短路径，使用严格条件 < 时通常只保留最先发现的一条。若需要记录所有最短路径前驱，需要将 parent[v] 改为前驱集合。

11. 常见错误

11.1 在含负权边的图上使用 Dijkstra

错误原因：已经确定的顶点可能被负权边再次改进。

解决方法：改用 Bellman-Ford Algorithm。

11.2 把无向边只加入一个方向

无向边 (u,v,w) 必须同时加入：

adj[u].append((v, w))  
adj[v].append((u, w))

11.3 忘记跳过堆中过期记录

使用重复入堆实现时，应检查：

if current_dist != dist[u]:  
    continue

否则虽然很多情况下仍能得到正确答案，但会重复处理顶点，降低效率。

11.4 使用 visited 后仍错误更新已确定顶点

一种规范做法是：

  • 使用 visited[u]，取出后若已访问则跳过；或

  • 不使用 visited，仅通过 current_dist != dist[u] 跳过过期记录。

两种方式均可，但不要混用出逻辑矛盾。

11.5 无穷大与溢出问题

伪代码中使用 ∞\infty。程序实现时：

  • Python 可使用 float("inf")；

  • 固定宽度整数语言应避免 INF + weight 发生溢出；

  • 松弛前先检查 dist[u] != INF。

11.6 只输出距离，没有维护前驱

若题目要求具体路径，必须维护 parent 数组。

12. 与其他最短路径算法的比较

算法解决问题是否允许负权边是否检测负权环典型复杂度
BFS无权图或等权图单源最短路不涉及否O(∥V∥+∥E∥)O(\|V\|+\|E\|)
Dijkstra非负权图单源最短路否否O((∥V∥+∥E∥)log⁡∥V∥)O((\|V\|+\|E\|)\log\|V\|)
Bellman–Ford一般加权图单源最短路是是O(∥V∥E∥)O(\|V\|E\|)
Floyd–Warshall所有点对最短路是可辅助判断O(∥V∥3)O(\|V\|^3)

选择规则

  • 无权图：优先使用 BFS；

  • 边权非负的单源最短路：优先使用 Dijkstra；

  • 存在负权边：使用 Bellman–Ford；

  • 顶点较少且要求所有点对距离：可考虑 Floyd–Warshall。

参考资料

  1. Dijkstra, E. W. (1959). A Note on Two Problems in Connexion with Graphs. Numerische Mathematik, 1, 269–271.

  2. Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.), Chapter 24. MIT Press.

  3. Demaine, E. D., & Leiserson, C. E. (2005). Introduction to Algorithms, Lecture 15: Shortest Paths I. MIT.

复习检查：

  • 能否解释为什么负权边会破坏贪心选择？
  • 能否独立写出松弛操作？
  • 能否区分邻接矩阵与邻接表实现的复杂度？
  • 能否使用 parent 数组恢复最短路径？
文章大纲
  1. Dijkstra 最短路径算法
  2. 目录
  3. 1. 问题定义
  4. 2. 基本思想
  5. 3. 需要问题具有的性质
  6. 3.1 边权必须非负
  7. 3.2 问题具有最优子结构
  8. 3.3 图可以是有向图或无向图
  9. 3.4 图不要求连通
  10. 4. 核心操作：松弛
  11. 5. 具体过程
  12. 5.1 初始化
  13. 5.2 选择当前最近顶点
  14. 5.3 松弛邻接边
  15. 5.4 终止
  16. 6. 伪代码
  17. 6.1 邻接表 + 最小堆
  18. 6.2 路径恢复
  19. 7. 正确性要点
  20. 8. 时空间复杂度
  21. 8.1 邻接矩阵 + 顺序查找最小值
  22. 8.2 邻接表 + 二叉最小堆
  23. 8.3 Fibonacci 堆
  24. 8.4 复杂度总结
  25. 9. 典型例子
  26. 9.1 图结构
  27. 9.2 初始化
  28. 9.3 执行过程
  29. 9.4 最短路径结果
  30. 10. 路径恢复
  31. 11. 常见错误
  32. 11.1 在含负权边的图上使用 Dijkstra
  33. 11.2 把无向边只加入一个方向
  34. 11.3 忘记跳过堆中过期记录
  35. 11.4 使用 visited 后仍错误更新已确定顶点
  36. 11.5 无穷大与溢出问题
  37. 11.6 只输出距离，没有维护前驱
  38. 12. 与其他最短路径算法的比较
  39. 参考资料
  40. 复习检查：