0Pricing
DSA Interview Prep · 课时

使用优先队列的 Dijkstra 算法

使用 heapq 实现 Dijkstra 算法，在带权图上跟踪松弛步骤，并解决 k 站以内的最低价航班问题。

使用优先队列的 Dijkstra 算法 是 CoddyKit 上的免费 DSA Interview Prep 课时。 这是第 1 节课，共 4 节。 你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。 这是 DSA Interview Prep 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 DSA Interview Prep 课程共包含 4 节课。

带权图中的最短路径

Dijkstra 算法用于在边权非负的带权图中，寻找从单个源节点到所有其他节点的最短路径。它会按照当前已知的最佳距离，以贪心方式处理节点——始终扩展距离最近的未访问节点。核心数据结构是最小堆（优先队列），它可以高效地取出距离最小的节点。

算法步骤概览

Dijkstra 算法：(1) 初始化 dist[source] = 0，并将 dist[all others] = inf。(2) 将 (0, source) 放入最小堆。(3) 弹出距离最小的节点 u。如果该节点此前已经以更小的距离访问过，则跳过它。(4) 对于 u 的每个邻居 v：如果 dist[u] + weight(u,v) < dist[v]，就更新 dist[v]，并将 (dist[v], v) 放入堆中。(5) 重复上述过程，直到堆为空。

使用 heapq 的 Python 实现

Python 的 heapq 实现了最小堆。我们使用邻接表表示图：graph[u] = [(v, weight), ...]。堆中存储 (distance, node) 元组。我们使用 visited 集合跳过过时的堆条目——这些条目是在找到更优路径之前放入堆中的。

import heapq

def dijkstra(graph, source):
    n = len(graph)
    dist = [float('inf')] * n
    dist[source] = 0
    heap = [(0, source)]  # (distance, node)
    visited = set()
    
    while heap:
        d, u = heapq.heappop(heap)
        if u in visited:
            continue
        visited.add(u)
        
        for v, weight in graph[u]:
            if dist[u] + weight < dist[v]:
                dist[v] = dist[u] + weight
                heapq.heappush(heap, (dist[v], v))
    
    return dist

完整示例

考虑一个包含 5 个节点的图，其边为：0→1 (4)、0→2 (1)、2→1 (2)、1→3 (1)、2→3 (5)、3→4 (3)。从节点 0 出发的最短路径为：到节点 1 的路径为 0→2→1，代价为 3；到节点 2 的代价为 1；到节点 3 的路径为 0→2→1→3，代价为 4；到节点 4 的路径为 0→2→1→3→4，代价为 7。Dijkstra 一次遍历就能找到所有这些路径，而不只是找到通往某个目标节点的路径。

import heapq

def dijkstra(graph, source):
    dist = [float('inf')] * len(graph)
    dist[source] = 0
    heap = [(0, source)]
    visited = set()
    while heap:
        d, u = heapq.heappop(heap)
        if u in visited:
            continue
        visited.add(u)
        for v, w in graph[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                heapq.heappush(heap, (dist[v], v))
    return dist

graph = [
    [(1,4),(2,1)],  # 0
    [(3,1)],         # 1
    [(1,2),(3,5)],   # 2
    [(4,3)],         # 3
    []               # 4
]
print(dijkstra(graph, 0))  # [0, 3, 1, 4, 7]

负权边下戴克斯特拉算法为何失效

戴克斯特拉算法的正确性依赖于这样一个事实：节点一旦从最小堆中弹出，其距离就已经确定。只有当边权为非负时，这一结论才成立。假设存在一条权重为 -5 的负边 u→v，访问 v 后，我们可能通过 u 找到一条更短的路径——但此时 v 已经被标记为已访问。单条负边就可能使后续所有距离计算失效。

最多 K 次中转的最低票价航班（LeetCode 787）

这道题增加了一个限制：最多只能有 k 个中转站。标准的戴克斯特拉算法无法原生处理步数。解决方案是将状态扩展为 (cost, node, stops_remaining)。可以使用这个三元组运行戴克斯特拉算法，也可以使用进行 k+1 轮松弛的贝尔曼-福特算法。修改后的戴克斯特拉算法会在 stops_remaining 达到 0 时停止，从而防止继续经过更多边。

import heapq
from collections import defaultdict

def findCheapestPrice(n, flights, src, dst, k):
    graph = defaultdict(list)
    for u, v, w in flights:
        graph[u].append((v, w))
    
    heap = [(0, src, k + 1)]  # (cost, node, hops_left)
    visited = {}  # node -> min hops_left seen at this cost level
    
    while heap:
        cost, node, hops = heapq.heappop(heap)
        if node == dst:
            return cost
        if hops == 0:
            continue
        if visited.get(node, 0) >= hops:
            continue
        visited[node] = hops
        for nxt, w in graph[node]:
            heapq.heappush(heap, (cost + w, nxt, hops - 1))
    return -1

print(findCheapestPrice(4,[[0,1,100],[1,2,100],[0,2,500]],0,2,1))  # 200

时间复杂度分析

使用二叉堆时，戴克斯特拉算法的运行时间为 O((V + E) log V)：每个顶点都会被弹出一次（V 次弹出），每条边都可能触发一次压入（E 次压入），而每次堆操作的成本为 O(log V)。使用斐波那契堆时，界限可以改进为 O(E + V log V)，但 Python 的 heapq 是二叉堆。对于稀疏图（E ≈ V），二叉堆版本的复杂度为 O(V log V)；对于稠密图（E ≈ V²），复杂度为 O(V² log V)。

重建最短路径

要恢复实际路径（而不仅仅是距离），请维护一个 prev 数组：更新 dist[v] 时，将 prev[v] = u。算法完成后，通过反向追踪从源点到目标点重建路径：从 dst 开始，沿着 prev 指针追踪，直到到达 source，然后将结果反转。

import heapq

def dijkstra_path(graph, source, target):
    n = len(graph)
    dist = [float('inf')] * n
    prev = [-1] * n
    dist[source] = 0
    heap = [(0, source)]
    visited = set()
    while heap:
        d, u = heapq.heappop(heap)
        if u in visited: continue
        visited.add(u)
        for v, w in graph[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                prev[v] = u
                heapq.heappush(heap, (dist[v], v))
    # Reconstruct
    path, node = [], target
    while node != -1:
        path.append(node)
        node = prev[node]
    return dist[target], path[::-1]

使用字典处理稀疏图

当节点是字符串或不连续的整数时，请使用 defaultdict(list) 表示邻接表，并使用普通的 dict 保存距离。在 Network Delay Time 等 LeetCode 题目中，这种做法很常见，其中节点的编号为 1 到 n。请记得使用 dist = {node: inf for node in all_nodes}，并在算法结束后检查是否存在不可达节点。

import heapq
from collections import defaultdict

def networkDelayTime(times, n, k):
    graph = defaultdict(list)
    for u, v, w in times:
        graph[u].append((v, w))
    
    dist = {i: float('inf') for i in range(1, n+1)}
    dist[k] = 0
    heap = [(0, k)]
    
    while heap:
        d, u = heapq.heappop(heap)
        if d > dist[u]: continue
        for v, w in graph[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                heapq.heappush(heap, (dist[v], v))
    
    ans = max(dist.values())
    return ans if ans < float('inf') else -1

print(networkDelayTime([[2,1,1],[2,3,1],[3,4,1]], 4, 2))  # 2

无权图与 BFS 的比较

对于无权图，BFS 能以 O(V + E) 的复杂度找到最短路径，比复杂度为 O((V+E) log V) 的戴克斯特拉算法更快。戴克斯特拉算法通过使用优先队列而不是普通的 FIFO 队列，将 BFS 推广到了带权图。当所有边权都相等时，戴克斯特拉算法会退化为 BFS。无权图请选择 BFS，非负权图请选择戴克斯特拉算法，负权图请选择贝尔曼-福特算法。

带减键优化的戴克斯特拉算法

教材中的戴克斯特拉算法使用带减键操作的优先队列：当某个节点的距离变小时，就原地更新其优先级。这需要使用斐波那契堆才能达到 O(E + V log V) 的复杂度，但实现起来很困难。面试中使用的延迟删除方法则会压入一个新条目，并跳过过期的弹出结果——实现更简单，只有常数级的额外开销。在 Python 中，使用 heapq 实现延迟删除是面试中的标准写法。

快速检查

请测试您对本课中“数据结构与算法——编码面试准备”相关概念的理解。

课程回顾

本课学习了以下内容：戴克斯特拉算法使用最小堆，按照当前最短距离的顺序贪心地处理节点；它的运行时间为 O((V+E) log V)，并且无法处理负权边；通过在弹出节点时检查已访问集合，可以处理堆中的过期条目。接下来将学习贝尔曼-福特算法，它通过 n-1 轮松弛处理负权边。

常见问题解答

「使用优先队列的 Dijkstra 算法」课时是免费的吗？

是的 — 「使用优先队列的 Dijkstra 算法」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 DSA Interview Prep 课程的其余内容，请升级到 CoddyKit PRO。 DSA Interview Prep 课程共包含 4 节课。

「使用优先队列的 Dijkstra 算法」这节课中我会学到什么？

使用 heapq 实现 Dijkstra 算法，在带权图上跟踪松弛步骤，并解决 k 站以内的最低价航班问题。 你通过在浏览器中直接运行的动手代码来练习 DSA Interview Prep，全天候 AI 导师会在你学习这节课的过程中回答你的问题。

学习 DSA Interview Prep 需要有经验吗？

无需任何先前经验。CoddyKit 上的 DSA Interview Prep 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。 这是第 1 节课，共 4 节。

「使用优先队列的 Dijkstra 算法」课时需要多长时间？

大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。

我能在这节 DSA Interview Prep 课中编写并运行代码吗？

能。每节 DSA Interview Prep 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。

此课程中的所有课时

  1. 使用优先队列的 Dijkstra 算法
  2. Bellman-Ford 与负环
  3. Floyd-Warshall：所有点对最短路径
  4. 网络延迟时间与路径重建
← 返回 DSA Interview Prep