第 43 课 - Dijkstra 最短路径

1. 学习目标

完成本课学习后，你将能够：

理解 Dijkstra 算法解决“单源最短路径”问题的核心思想和过程。
掌握使用优先队列（堆）优化的 Dijkstra 算法的具体实现。
分析 Dijkstra 算法的时间复杂度及其适用场景。
了解贪心算法思想在 Dijkstra 算法中的体现。
识别 Dijkstra 算法的局限性（例如，不能处理负权边）。

2. 核心概念

想象一下，你站在地图上的一个起点（源点），想要找到到达所有其他地点的最短距离。Dijkstra 算法就像一个非常聪明的“导航仪”。

它的核心思想是 “贪心”：每次从当前 “已确定最短路径” 的节点集合中，选择一个距离源点最近的节点 u。然后，将这个节点 u 标记为“已确定”，并用它去 “松弛” 它的所有邻居节点 v。

“松弛”（Relaxation） 是一个关键操作：如果通过节点 u 到达邻居 v 的路径，比之前已知的到 v 的路径更短，就更新 v 的距离。

整个过程，我们需要一个数据结构来快速找到“当前距离源点最近的未确定节点”。这就是 优先队列（通常用最小堆实现） 的用武之地，它使得这个查找和更新操作非常高效。

算法流程简述：

初始化：源点距离设为0，其他所有节点距离设为无穷大。将所有节点放入一个最小堆（优先队列）。
循环：当堆不为空时，弹出堆顶元素（即当前距离源点最近的未确定节点 u）。
如果弹出的 u 的距离大于已记录的 dist[u]，则跳过（因为这是“过时”的信息）。
将 u 标记为已确定（其实隐含在步骤2-3中）。
对于 u 的每个邻居 v 和它们之间的边权 weight，执行松弛操作：如果 dist[u] + weight < dist[v]，则更新 dist[v] = dist[u] + weight，并将 (新的dist[v], v) 推入堆中。

3. 代码示例

下面是一个使用 Python 实现的、基于优先队列（heapq）优化的 Dijkstra 算法。

import heapq

def dijkstra(graph, start):
    """
    使用优先队列（最小堆）优化的 Dijkstra 算法
    :param graph: 图的邻接表表示。graph[u] 是一个列表，包含 (v, weight) 元组。
    :param start: 源点
    :return: 一个字典，包含从 start 到所有其他节点的最短距离
    """
    # 1. 初始化
    distances = {node: float('inf') for node in graph} # 所有距离初始为无穷大
    distances[start] = 0 # 源点到自己的距离为0
    # 优先队列中存储 (距离， 节点) 元组
    priority_queue = [(0, start)]
    # 记录节点是否已处理（已确定最短路径），用于跳过“过时”条目
    visited = set()

    # 2. 主循环
    while priority_queue:
        # 2.1 弹出当前距离源点最近的节点
        current_distance, current_node = heapq.heappop(priority_queue)

        # 2.2 如果当前节点已经处理过，或者其距离大于已记录的距离，则跳过
        if current_node in visited:
            continue
        # 标记为已确定
        visited.add(current_node)

        # 2.3 对当前节点的所有邻居进行松弛操作
        for neighbor, weight in graph[current_node]:
            distance = current_distance + weight

            # 2.3.1 松弛操作：如果找到更短路径，则更新距离并加入队列
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(priority_queue, (distance, neighbor))

    return distances

# 测试代码
if __name__ == "__main__":
    # 创建一个图的邻接表
    # 图结构: 0 -- (1) --> 1 -- (2) --> 2 -- (3) --> 3
    #         \          ^           /
    #          (4)     (1)        (5)
    #            \    /          /
    #              4 ----------/
    graph = {
        0: [(1, 1), (4, 4)],
        1: [(2, 2)],
        2: [(3, 3)],
        3: [],
        4: [(1, 1), (2, 5)]
    }
    start_node = 0
    shortest_distances = dijkstra(graph, start_node)

    print(f"从节点 {start_node} 到各节点的最短距离:")
    for node, dist in sorted(shortest_distances.items()):
        print(f"到节点 {node}: {dist}")

预期输出：

从节点 0 到各节点的最短距离:
到节点 0: 0
到节点 1: 1
到节点 2: 3
到节点 3: 6
到节点 4: 4

解释：到节点2的最短路径是 0->1->2 (1+2=3)，而不是 0->4->2 (4+5=9)。到节点3的最短路径是 0->1->2->3 (1+2+3=6)。

4. 实践练习

练习1：基础应用

题目：给定一个城市的地铁网络图（无向图），站点用字母A, B, C...表示，边上的数字代表两站之间的通行时间（分钟）。从站点A出发，使用 Dijkstra 算法计算到所有其他站点的最短时间。

图：

A --2-- B --3-- C
|       |       |
1       5       1
|       |       |
D --1-- E --2-- F

要求：使用上述代码模板，构建对应的图数据结构并运行算法。 预期输出：打印出从A到A, B, C, D, E, F的最短时间。

练习2：路径重构（进阶）

题目：在练习1的基础上，不仅计算最短距离，还要能输出从源点到任意节点的具体最短路径（如：A -> D -> E -> B）。要求：修改 dijkstra 函数，使其除了返回距离字典 distances，还能返回一个 predecessors 字典，记录每个节点在最短路径上的前驱节点。编写一个 get_path 函数，根据 predecessors 重构路径。提示：在更新 distances[neighbor] 时，同时记录 predecessors[neighbor] = current_node。

练习3：理解限制

题目：如果图中存在负权边，Dijkstra 算法可能会失效。请构造一个包含3-4个节点的简单图示例（其中有负权边），手动模拟 Dijkstra 算法的过程，并说明它为什么会得出错误的结果。要求：画出你的图，并写出源点、算法步骤和错误结果。

5. 常见错误

忘记处理负权边：这是 Dijkstra 算法最根本的局限性。贪心策略基于“已确定的节点距离不会再变小”，但负权边可能使得通过一个已确定节点，再绕到另一个节点，得到更小的距离。此时需要使用 Bellman-Ford 算法。
初始化错误：所有节点的距离初始化为无穷大（float('inf')），源点距离初始化为0。如果源点初始化错误，整个算法会出错。
优先队列更新处理不当：在代码实现中，我们可能会向队列中多次插入同一个节点（距离不同）。必须通过 if current_node in visited: continue 这一步来忽略那些“过时”的、距离更大的旧条目。这是避免重复处理的关键。
图的表示错误：确保邻接表构建正确。对于无向图，每条边 u-v 应该在 graph[u] 和 graph[v] 中各添加一条记录。
不正确的松弛条件：松弛的条件是 dist[u] + weight < dist[v]，必须是严格小于才更新。如果等于，通常不更新（除非你需要计算所有最短路径）。

6. 小结

Dijkstra 算法 是解决单源最短路径问题的经典算法，适用于边权非负的图。
核心思想是贪心：每次从未确定最短路径的节点中，选择距离源点最近的节点进行扩展和松弛。
使用优先队列（最小堆） 实现可以将时间复杂度优化至 O((V+E) log V)，其中 V 是节点数，E 是边数。
算法成功的关键在于它保证：当一个节点被从优先队列中弹出时，它的最短距离就已经被最终确定了（前提是无负权边）。
它的局限性在于无法处理包含负权边的图，这类问题需要其他算法（如 Bellman-Ford）解决。

练习编辑器

rust