CC++ & Algorithm

Python最短路径 Dijkstra 算法

较难2
语言版本：C++Python
概述：从起点出发，像“贪吃蛇”一样每次去最近的新地点，并记下到达每个地点的最短距离，最终得到从起点到所有地点的最短路径。

Dijkstra 算法：像贪吃蛇一样寻找最短路径

这个算法有什么用？

我们经常在地图导航中看到“从家到学校最短距离是多少？”这样的问题。Dijkstra算法就是计算机用来解决从一个起点到图中所有其他点的最短路径的经典算法。它只适用于所有道路长度（边的权重）都是非负数的情况。

想想看：如果你站在城市中心，想知道去每个小区的最短驾车距离，你会怎么办？Dijkstra算法就像一个聪明的“贪吃蛇”，每次从没去过的地方中挑一个离你最近的，然后从这个新地方出发，看看能不能让去邻居的路线变得更短。重复这个过程，最终就能得到从起点到所有地方的真实最短距离。

生活中的比喻：从家出发找最短路线

假设你家在城市中心（0号位置），周围有若干个地点，比如学校（1号）、超市（2号）、电影院（3号）和游乐园（4号）。道路连接如下：

  • 家到学校：10公里
  • 家到超市：15公里
  • 学校到超市：5公里
  • 学校到电影院：12公里
  • 超市到电影院：8公里
  • 超市到游乐园：7公里
  • 电影院到游乐园：3公里

Dijkstra算法会这样做：

  1. 在家门口贴上“0公里”的标签，其他所有地方暂时贴上“∞（无穷大）”。
  2. 现在没去过的地方中，最近的是家（0公里），所以先出发去家（已经在了），然后从家出发看邻居：去学校可以缩短到10公里（原来∞），去超市缩短到15公里。更新标签。
  3. 现在没去过的地方中，距离最小的是学校（10公里），所以下一站去学校。到了学校，发现从学校去超市只要 10+5=15公里，和原来一样，不用改；去电影院 10+12=22公里，比原来的∞小，所以电影院更新为22公里。
  4. 下一步没去过中最小的是超市（15公里），去超市，从超市去电影院 15+8=23，比22大，不更新；去游乐园 15+7=22，更新游乐园为22。
  5. 然后没去过中最小的是电影院（22公里）和游乐园（22公里），随便选一个，比如先去电影院，从电影院去游乐园 22+3=25，比22大，不更新。
  6. 最后去游乐园（22公里），没有邻居未处理了。算法结束。

最终标签：家0，学校10，超市15，电影院22，游乐园22。这就是从家到每个地方的最短距离。

核心思想：贪心策略 + 放松操作

Dijkstra算法的核心是贪心：每次选择当前已知距离最小的未处理节点，认为这个节点的距离已经是最终最短距离了（因为所有边非负，不可能通过其他路径再缩短）。然后对这个节点的所有邻居进行“放松”操作——就是检查“经过当前节点去邻居会不会比原来已知的距离更短”，如果是就更新邻居的距离。

这个“贪心”策略很符合直觉：就像你从家出发，肯定会先去最近的一个地方，到了那里之后，再考虑从这里出发去其他地方会不会更近。

为什么需要优先队列（最小堆）

如果每次都要遍历所有节点找出距离最小的未处理节点，程序会非常慢（需要O(n²)时间）。使用最小堆（优先队列）可以快速取出最小元素，并且插入新元素也很快（O(log n)）。

想象一下：你有一堆贴在墙上的便签，每个便签写着某个地方的距离数字。你每次都要翻遍所有便签找出最小的数字，非常麻烦。但如果把这些便签按数字从小到大堆成一摞，每次直接拿最上面的那张就行了。最小堆就是这个作用。

算法步骤详解

  1. 初始化：将起点的距离设为0，其他所有点的距离设为无穷大（表示还不知道怎么到达）。
  2. 建立最小堆：堆中放入(距离, 节点)对，起点优先。
  3. 循环直到堆为空：
    • 从堆中弹出距离最小的节点（记为 u）。
    • 如果弹出的距离大于当前记录的距离（说明这个记录已经过时，比如之前旧的距离被弹出），则跳过（因为后面已经更新了更短的距离）。
    • 对于 u 的每个邻居 v，计算从起点经过 u 到 v 的新距离 = dist[u] + 边的权重。
    • 如果新距离小于 dist[v]，则更新 dist[v] 为新值，并将 (新距离, v) 压入堆中（注意：原来的旧记录还在堆里，但我们之后会通过“跳过过时记录”来处理）。
  4. 返回最终的距离数组。

代码逐行解析（含中文注释）

下面代码基于邻接表存储图，每个节点 u 对应一个列表 adj[u]，列表中的元素是 (邻居节点, 边的权重)。

import heapq

def dijkstra(n, adj, start):
    """
    参数：
        n: 节点数量（节点编号0~n-1）
        adj: 邻接表，adj[u] = [(v1, w1), (v2, w2), ...]
        start: 起点节点编号
    返回：dist列表，dist[i]表示从起点到i的最短距离
    """
    dist = [float('inf')] * n      # 距离数组，初始为无穷大
    dist[start] = 0                # 起点到自身的距离为0
    heap = [(0, start)]            # 最小堆，每个元素是(距离, 节点)

    while heap:                    # 只要堆中还有节点待处理
        d, u = heapq.heappop(heap) # 取出当前距离最小的节点
        if d > dist[u]:            # 如果这个记录已经过时（不是最新距离），跳过
            continue
        for v, w in adj[u]:        # 遍历节点u的所有邻居
            new_d = d + w          # 从起点经过u到v的距离
            if new_d < dist[v]:    # 如果这个路线更短
                dist[v] = new_d    # 更新v的最短距离
                heapq.heappush(heap, (new_d, v)) # 将新距离加入堆（旧记录以后会被跳过）
    return dist

关键点说明

  • if d > dist[u]: continue 非常重要！因为同一个节点可能被多次加入堆（第一次是10公里，后来发现更短变成8公里，又加了一次），堆中会有 (10, u) 和 (8, u) 两个。当弹出 (10, u) 时，当前的 dist[u] 已经是8，所以 10 > 8，说明这个记录已经过时了，直接忽略。
  • 所有边权重必须非负，否则算法失效。

生活中的例子完整走一遍（用代码模拟）

我们还是用之前那张城市地图（5个节点，0是家），来手动模拟算法过程。假设邻接表如下：

节点 u邻居列表
0(1, 10), (2, 15)
1(0, 10), (2, 5), (3, 12)
2(0, 15), (1, 5), (3, 8), (4, 7)
3(1, 12), (2, 8), (4, 3)
4(2, 7), (3, 3)

初始状态：dist = [0, ∞, ∞, ∞, ∞]，堆 = [(0, 0)]。

第1次循环：弹出 (0, 0)，d=0，dist[0]=0，不跳过。遍历邻居：

  • 邻居1：new_d=0+10=10 < ∞ → dist[1]=10，堆加入(10,1)
  • 邻居2：new_d=0+15=15 < ∞ → dist[2]=15，堆加入(15,2)

现在堆：[(10,1), (15,2)]，dist = [0, 10, 15, ∞, ∞]

第2次循环：弹出 (10,1)，d=10，dist[1]=10，不跳过。遍历邻居：

  • 邻居0：new_d=10+10=20 > dist[0]=0，不更新
  • 邻居2：new_d=10+5=15 == dist[2]=15，不更新（等于也不更新，因为我们是“小于”才更新）
  • 邻居3：new_d=10+12=22 < ∞ → dist[3]=22，堆加入(22,3)

堆：[(15,2), (22,3)]，dist = [0, 10, 15, 22, ∞]

第3次循环：弹出 (15,2)，d=15，dist[2]=15，不跳过。遍历邻居：

  • 邻居0：new_d=15+15=30 > 0
  • 邻居1：new_d=15+5=20 > 10
  • 邻居3：new_d=15+8=23 > 22
  • 邻居4：new_d=15+7=22 < ∞ → dist[4]=22，堆加入(22,4)

堆：[(22,3), (22,4)]，dist = [0, 10, 15, 22, 22]

第4次循环：弹出 (22,3)，d=22，dist[3]=22，不跳过。遍历邻居：

  • 邻居1：new_d=22+12=34 > 10
  • 邻居2：new_d=22+8=30 > 15
  • 邻居4：new_d=22+3=25 > 22，不更新

堆：[(22,4)]，dist不变。

第5次循环：弹出 (22,4)，d=22，dist[4]=22，不跳过。遍历邻居：

  • 邻居2：new_d=22+7=29 > 15
  • 邻居3：new_d=22+3=25 > 22

堆为空，算法结束。最终dist = [0, 10, 15, 22, 22]。

结果：从家到学校10公里，到超市15公里，到电影院和游乐园都是22公里。

常见错误与陷阱

1. 忘记了“跳过过时记录”的条件

很多新手写的代码没有 if d > dist[u]: continue，结果当同个节点多次入堆后，会错误地处理旧的、较大的距离，导致更新邻居时使用错误的值，甚至可能死循环。

2. 在堆中更新距离时，没有同时添加新记录

有人试图修改堆中已有的元素，但堆不支持直接修改。正确做法是把新距离作为一个新元素压入堆，然后通过“跳过过时记录”忽略旧元素。

3. 图中有负权边

如果存在负权边，Dijkstra算法会得出错误结果。例如：起点A到B权5，A到C权2，C到B权-3。算法先选C（距离2），更新B为2+(-3)=-1，但实际经过A直接到B是5，-1比5小，但此时B被错误地标记为-1，而实际上从C到B的边是负权，可能导致后面再通过B更新其他节点时产生混乱。Dijkstra算法要求所有边权非负。

4. 初始化距离为0错误

除了起点，其他点初始化为0？那样算法会认为所有点都已经最近，直接结束。所以一定要初始化为无穷大。

5. 图不连通时，距离为∞

如果有些节点从起点无法到达，算法结束后它们的dist值仍然是 float('inf')。代码中要处理这种情况，不能直接用于计算。

完整可运行示例：不仅输出距离，还输出路径

在实际应用（比如游戏寻路、地图导航）中，我们不仅要知道最短距离，还要知道怎么走。可以在算法中记录每个节点的前驱节点，最后通过回溯得到路径。

import heapq

def dijkstra_with_path(n, adj, start):
    """
    返回两个列表：
        dist: 最短距离
        parent: 前驱节点，-1表示起点或无前驱
    """
    dist = [float('inf')] * n          # 距离数组，初始无穷大
    parent = [-1] * n                   # 前驱节点数组，-1表示无
    dist[start] = 0                     # 起点距离为0
    heap = [(0, start)]                 # 最小堆，元素(距离, 节点)

    while heap:
        d, u = heapq.heappop(heap)      # 取出当前距离最小的节点
        if d > dist[u]:                  # 跳过过时记录
            continue
        for v, w in adj[u]:              # 遍历邻居
            new_d = d + w
            if new_d < dist[v]:          # 发现更短路径
                dist[v] = new_d
                parent[v] = u            # 记录v的前驱是u
                heapq.heappush(heap, (new_d, v))
    return dist, parent

def get_path(parent, target):
    """根据parent数组，从target回溯到起点，返回路径列表"""
    path = []
    while target != -1:                  # 一直追溯到起点（起点的parent为-1）
        path.append(target)
        target = parent[target]
    return path[::-1]                    # 反转，从起点到终点

# 示例：使用前文的地图
graph_adj = [
    [(1, 10), (2, 15)],          # 节点0（家）
    [(0, 10), (2, 5), (3, 12)],  # 节点1（学校）
    [(0, 15), (1, 5), (3, 8), (4, 7)], # 节点2（超市）
    [(1, 12), (2, 8), (4, 3)],   # 节点3（电影院）
    [(2, 7), (3, 3)]             # 节点4（游乐园）
]

start_node = 0
dist, parent = dijkstra_with_path(5, graph_adj, start_node)

print("从家出发到各点的最短距离和路径：")
node_names = ["家", "学校", "超市", "电影院", "游乐园"]
for i in range(5):
    if dist[i] == float('inf'):
        print(f"到{node_names[i]}(节点{i})：不可到达")
    else:
        path = get_path(parent, i)
        path_names = [node_names[p] for p in path]
        print(f"到{node_names[i]}(节点{i})：最短距离 {dist[i]}，路径 {' -> '.join(path_names)}")

运行结果：

从家出发到各点的最短距离和路径：
到家(节点0)：最短距离 0，路径 家
到学校(节点1)：最短距离 10，路径 家 -> 学校
到超市(节点2)：最短距离 15，路径 家 -> 学校 -> 超市   （注意：虽然直接去超市15公里，但经过学校也是15，所以路径有两种可能，程序只记录了其中一条）
到电影院(节点3)：最短距离 22，路径 家 -> 学校 -> 电影院
到游乐园(节点4)：最短距离 22，路径 家 -> 学校 -> 超市 -> 游乐园

相关知识点

如果你对最短路径算法感兴趣，接下来可以学习：

  • Bellman-Ford算法：可以处理负权边，但速度较慢（O(n×m)）。如果图中可能有负权，就要用它。
  • Floyd-Warshall算法：可以计算所有节点对之间的最短路径，但需要O(n³)时间，适合小图。
  • A*算法：在Dijkstra基础上加入启发式估计，在给定目标点的情况下能更快找到路径（常用于游戏寻路）。
  • 最小生成树（Prim算法）：Prim算法和Dijkstra非常像，但Prim选择的是到树最近的点，而Dijkstra选择的是到起点最近的点，两者目标不同。

理解Dijkstra算法是学习图论最短路径的基础，掌握了它，你就能应对大部分经典路径规划问题了！

例题精讲

1单选题

在Dijkstra算法中，每次从尚未确定最短路径的顶点中选择一个顶点进行处理，该顶点的选择依据是下列哪一项？

A与起点连接边数最少的顶点
B当前距离起点最近的顶点
C与已处理顶点有直接边的任意顶点
D尚未处理顶点中编号最小的顶点
2单选题

Dijkstra算法不能处理含有负权边的图，主要原因是？

A算法无法处理有向图
B负权边会导致图中出现负环
C算法的贪心策略在负权边下可能失效
D负权边会使邻接矩阵表示法出错
3判断题

使用优先队列（最小堆）优化Dijkstra算法后，其时间复杂度为O((V+E)logV)，其中V为顶点数，E为边数。

4填空题
请补全以下堆优化的Dijkstra算法代码，实现从起点start到各点的最短距离计算。

import heapq

def dijkstra(graph, n, start):
    # graph: 邻接表，graph[u] = [(v, w), ...]
    INF = 10**9
    dist = [INF] * n
    dist[start] = 0
    pq = [(0, start)]  # (distance, vertex)
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]:
            continue
        for v, w in graph[u]:
            new_dist = dist[u] + w
            if new_dist < dist[v]:
                dist[v] = new_dist
                ___  # 请填入正确语句
    return dist
5单选题

关于Dijkstra算法的正确适用范围，以下说法正确的是？

A仅适用于无向图
B仅适用于有向无环图
C适用于所有带权图，包括负权图
D适用于边权非负的任意有向图或无向图