迪杰斯特拉有两种常见写法，一种是使用邻接矩阵的 朴素迪杰斯特拉，一种是使用最小堆的堆优化迪杰斯特拉，前者适合于稠密图，后者适合于稀疏图。

朴素迪杰斯特拉

这种写法在寻找需要加入的最近的点时，需要遍历所有未加入的点，每加入一个点都需要遍历一次，所以时间复杂度是 $O(V^2)$，空间复杂度是 $O(V)$。

堆优化迪杰斯特拉

这种写法通过维护一个距离当前已加入的点的最小堆，来寻找需要加入的最近的点，每次寻找需要 $O(\log E)$ 时间，时间复杂度是 $O(E\log E)$，空间复杂度是 $O(E)$。 由于在连通图中 $E \ge V-1$，分析复杂度时以 $E$ 为主。注意堆中会有重复节点，所以至多有 $O(E)$ 个元素，单次操作的复杂度是 $O(\log E)$。值得注意的是，如果输入的是稠密图，写法二的时间复杂度为 $O(V^2 \log V)$，（可能需要 $V^2$ 次取堆）不如写法一。

朴素迪杰斯特拉模板

from typing import List
import math

def naive_dijkstra(n: int, edges: List[List[int]], source: int) -> List[int]:
    """
    朴素迪杰斯特拉算法模板。
    
    参数:
    - n: 图中顶点的数量（假设顶点编号从 1 到 n）
    - edges: 图的边列表，每条边由 [u, v, w] 表示，从顶点 u 到顶点 v 的权重为 w
    - source: 源点的编号（从 1 开始）
    
    返回:
    - 一个列表，表示从源点到每个顶点的最短距离。如果某个顶点不可达，则对应位置为 math.inf
    """
    # 初始化邻接矩阵
    INF = math.inf
    graph = [[INF for _ in range(n)] for _ in range(n)]
    for u, v, w in edges:
        graph[u - 1][v - 1] = w  # 假设图是有向的，如需无向图，需添加 graph[v-1][u-1] = w
    
    # 初始化距离数组和访问数组
    distances = [INF] * n
    distances[source - 1] = 0  # 源点到自身的距离为 0
    visited = [False] * n
    
    while True:
        # 选择当前未访问且距离最小的顶点
        current = -1
        for i in range(n):
            if not visited[i] and (current == -1 or distances[i] < distances[current]):
                current = i
        
        if current == -1:
            break  # 所有可达顶点已访问完毕
        
        if distances[current] == INF:
            break  # 剩余顶点不可达
        
        # 标记当前顶点为已访问
        visited[current] = True
        
        # 更新当前顶点的邻居的距离
        for neighbor in range(n):
            if graph[current][neighbor] != INF:
                new_distance = distances[current] + graph[current][neighbor]
                if new_distance < distances[neighbor]:
                    distances[neighbor] = new_distance
    
    return distances

# 示例用法
if __name__ == "__main__":
    # 示例图：
    # 顶点数量
    n = 5
    # 边列表，每条边为 [起点, 终点, 权重]
    edges = [
        [1, 2, 10],
        [1, 3, 3],
        [2, 3, 1],
        [3, 2, 4],
        [2, 4, 2],
        [3, 4, 8],
        [3, 5, 2],
        [5, 4, 9],
        [4, 5, 7]
    ]
    # 源点
    source = 1
    # 计算最短距离
    shortest_distances = naive_dijkstra(n, edges, source)
    # 输出结果
    for i, dist in enumerate(shortest_distances, 1):
        print(f"从顶点 {source} 到顶点 {i} 的最短距离为: {dist if dist != math.inf else '不可达'}")

堆优化迪杰斯特拉模板

from typing import List
import math
import heapq

def heap_optimized_dijkstra(n: int, edges: List[List[int]], source: int) -> List[float]:
    """
    堆优化迪杰斯特拉算法模板。
    
    参数:
    - n: 图中顶点的数量（假设顶点编号从 1 到 n）
    - edges: 图的边列表，每条边由 [u, v, w] 表示，从顶点 u 到顶点 v 的权重为 w
    - source: 源点的编号（从 1 开始）
    
    返回:
    - 一个列表，表示从源点到每个顶点的最短距离。如果某个顶点不可达，则对应位置为 math.inf
    """
    # 初始化邻接表
    INF = math.inf
    graph = [[] for _ in range(n)]
    for u, v, w in edges:
        graph[u - 1].append((v - 1, w))  # 假设图是有向的，如需无向图，需添加 graph[v-1].append((u-1, w))
    
    # 初始化距离数组
    distances = [INF] * n
    distances[source - 1] = 0  # 源点到自身的距离为 0
    
    # 初始化优先队列 (堆)，存储 (距离, 顶点) 元组
    heap = [(0, source - 1)]
    
    while heap:
        current_distance, u = heapq.heappop(heap)
        
        # 如果当前距离大于已知最短距离，跳过
        if current_distance > distances[u]:
            continue
        
        # 遍历当前顶点的所有邻居
        for neighbor, weight in graph[u]:
            distance = current_distance + weight
            # 如果通过 u 到 neighbor 的距离更短，更新距离并将其加入堆中
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(heap, (distance, neighbor))
    
    return distances

# 示例用法
if __name__ == "__main__":
    # 示例图：
    # 顶点数量
    n = 5
    # 边列表，每条边为 [起点, 终点, 权重]
    edges = [
        [1, 2, 10],
        [1, 3, 3],
        [2, 3, 1],
        [3, 2, 4],
        [2, 4, 2],
        [3, 4, 8],
        [3, 5, 2],
        [5, 4, 9],
        [4, 5, 7]
    ]
    # 源点
    source = 1
    # 计算最短距离
    shortest_distances = heap_optimized_dijkstra(n, edges, source)
    # 输出结果
    for i, dist in enumerate(shortest_distances, 1):
        print(f"从顶点 {source} 到顶点 {i} 的最短距离为: {dist if dist != math.inf else '不可达'}")

问：为什么代码要判断 current_distance > distances[u] ？

答：对于同一个 u，例如先入堆一个比较大的 distance[u]=10，后面又把 distance[x] 更新成 5，之后这个 5 会先出堆，然后再把 10 出堆。10 出堆时候是没有必要去更新周围邻居的最短路的，因为 5 出堆之后，就已经把邻居的最短路更新过了，用 10 是无法把邻居的最短路变得更短的，所以直接 continue。

参考

• 灵神题解