图的最短路径：Dijkstra 算法的优先队列优化

图的最短路径问题是图论中的经典问题，旨在找到从源点到其他所有顶点的最短路径。Dijkstra 算法是一种高效算法，适用于边权重非负的图。标准实现使用数组存储距离，但时间复杂度较高（$O(V^2)$）。通过优先队列（如二叉堆）优化，可以将时间复杂度降至$O((V + E) \log V)$，显著提升效率。下面我将逐步解释算法原理、优化方法和实现。

1. Dijkstra 算法基础

Dijkstra 算法基于贪心策略，逐步松弛边以更新最短距离。假设图$G$有$V$个顶点和$E$条边，权重函数$w(u,v)$表示边$(u,v)$的权重。算法维护一个距离数组$d$，其中$d[v]$表示从源点$s$到顶点$v$的当前最短距离。初始化时：

• $d[s] = 0$
• $d[v] = \infty$（对于所有$v \neq s$）

算法重复以下步骤：

1. 选择未访问顶点中$d[u]$最小的顶点$u$。
2. 松弛所有从$u$出发的边：对于每个邻居$v$，如果$d[u] + w(u,v) < d[v]$，则更新$d[v] = d[u] + w(u,v)$。

标准实现中，查找最小$d[u]$需扫描整个数组，耗时$O(V)$，导致总时间$O(V^2)$。

2. 优先队列优化原理

优先队列优化使用最小堆（或类似数据结构）高效管理顶点距离。核心思想是：

• 将顶点及其当前距离存储为元组$(d[u], u)$。
• 堆总保持最小距离在顶部，提取最小元素仅需$O(\log V)$时间。
• 松弛边时，如果更新距离，则推入新条目到堆中（可能产生过时条目，但通过检查忽略）。

优化后，算法步骤：

1. 初始化距离数组$d$和堆（优先队列）。
2. 推入源点$(0, s)$到堆。
3. 循环直到堆空：
   • 弹出堆顶元素$(d[u], u)$。
   • 如果$d[u]$已过时（即$d[u]$不等于当前距离），则跳过。
   • 否则，松弛$u$的所有邻居：对于每个$(v, w)$，计算新距离$new_dist = d[u] + w$。
   • 如果$new_dist < d[v]$，更新$d[v] = new_dist$并推入$(new_dist, v)$到堆。
4. 返回距离数组$d$。

时间复杂度：每个顶点最多入堆一次，每条边最多触发一次堆操作。堆操作（插入和删除）为$O(\log V)$，因此总时间$O((V + E) \log V)$。空间复杂度$O(V)$。

3. Python 代码实现

以下代码使用 Python 的heapq模块实现优先队列优化。图以邻接列表表示：graph是列表的列表，其中graph[u]包含元组(v, weight)表示边$(u,v)$的权重。

import heapq

def dijkstra(graph, start):
    n = len(graph)  # 顶点数
    dist = [float('inf')] * n  # 初始化距离数组
    dist[start] = 0
    
    # 优先队列：存储元组 (当前距离, 顶点)
    heap = [(0, start)]
    
    while heap:
        d, u = heapq.heappop(heap)  # 弹出最小距离顶点
        # 跳过过时条目（d 不等于当前 dist[u]）
        if d != dist[u]:
            continue
        # 松弛所有邻居
        for v, weight in graph[u]:
            new_dist = dist[u] + weight
            # 如果找到更短路径，则更新并推入堆
            if new_dist < dist[v]:
                dist[v] = new_dist
                heapq.heappush(heap, (new_dist, v))
    
    return dist  # 返回从源点到所有顶点的最短距离

代码说明：

• 输入：graph 是图的邻接列表（例如，graph = [[(1, 4), (2, 1)], [(3, 2)], [], []] 表示顶点0到1权重4，到2权重1；顶点1到3权重2）。
• 输出：dist 列表，其中 dist[i] 是源点到顶点 $i$ 的最短距离。
• 关键优化：
  • 使用 heapq 实现最小堆，优先队列保证高效提取最小值。
  • 过时条目处理：当弹出元素时，检查其距离是否与当前 dist[u] 一致，不一致则跳过（避免多次更新）。
  • 松弛操作：只在新距离更小时更新，并推入堆中。

4. 复杂度分析与优势

• 时间复杂度：$O((V + E) \log V)$。每个顶点入堆一次（$O(V \log V)$），每条边可能触发一次堆操作（$O(E \log V)$）。优于标准 $O(V^2)$ 实现。
• 空间复杂度：$O(V)$，用于存储距离和堆。
• 优势：
  • 高效处理稀疏图（$E \ll V^2$）。
  • 实际应用广泛，如路由算法和网络优化。
  • 易于实现，使用标准库（如 Python 的 heapq）。

5. 总结

Dijkstra 算法的优先队列优化通过最小堆管理顶点距离，显著降低时间复杂度。代码实现简洁，适合处理大规模图。记住，该算法要求边权重非负；若权重可为负，需使用 Bellman-Ford 算法。您可以根据实际图结构调整代码输入格式。