LeetCode Dijkstra 算法题解题目描述Dijkstra 算法是一种用于解决单源最短路径问题的贪心算法。它可以在加权图中找到从源节点到其他所有节点的最短路径前提是边的权重都是非负的。示例对于以下加权图A --(2)-- B --(4)-- C | | | (1) (3) (1) | | | D --(5)-- E --(2)-- F从 A 出发到各节点的最短路径长度为A → D: 1A → B: 2A → E: 156 或 A→B→E: 235更短A → C: 246A → F: 2327 或 A→B→C→F: 2417解题思路方法Dijkstra 算法思路Dijkstra 算法的核心思想是使用贪心策略每次选择当前距离源节点最近的未访问节点然后更新其相邻节点的距离。具体步骤初始化一个距离数组源节点的距离为 0其他节点的距离为无穷大。使用优先队列最小堆来存储未访问的节点及其距离。从源节点开始每次从优先队列中取出距离最小的节点标记为已访问。对于该节点的每个相邻节点计算通过当前节点到达该相邻节点的距离如果这个距离比已知的距离小则更新距离并将相邻节点加入优先队列。重复步骤 3-4直到优先队列为空。复杂度分析时间复杂度O((V E) log V)其中 V 是顶点数E 是边数。每个顶点和边都会被处理一次优先队列的操作时间为 O(log V)。空间复杂度O(V E)需要存储图的邻接表和距离数组。代码实现方法Dijkstra 算法import heapq # Dijkstra 算法 def dijkstra(graph, start): # 初始化距离字典源节点的距离为 0其他节点的距离为无穷大 distances {node: float(infinity) for node in graph} distances[start] 0 # 使用优先队列最小堆来存储未访问的节点及其距离 priority_queue [(0, start)] # 记录已访问的节点 visited set() while priority_queue: # 取出距离最小的节点 current_distance, current_node heapq.heappop(priority_queue) # 如果节点已经访问过跳过 if current_node in visited: continue # 标记为已访问 visited.add(current_node) # 遍历当前节点的所有相邻节点 for neighbor, weight in graph[current_node].items(): # 计算通过当前节点到达相邻节点的距离 distance current_distance weight # 如果这个距离比已知的距离小更新距离并将相邻节点加入优先队列 if distance distances[neighbor]: distances[neighbor] distance heapq.heappush(priority_queue, (distance, neighbor)) return distances # 测试 def test_dijkstra(): # 构建图结构邻接表 graph { A: {B: 2, D: 1}, B: {A: 2, C: 4, E: 3}, C: {B: 4, F: 1}, D: {A: 1, E: 5}, E: {B: 3, D: 5, F: 2}, F: {C: 1, E: 2} } # 测试从 A 出发的最短路径 print(Shortest distances from A:) distances dijkstra(graph, A) for node, distance in distances.items(): print(f{node}: {distance}) # 输出 # A: 0 # B: 2 # D: 1 # E: 5 # C: 6 # F: 7 if __name__ __main__: test_dijkstra()测试用例测试用例从 A 出发的最短路径输入A --(2)-- B --(4)-- C | | | (1) (3) (1) | | | D --(5)-- E --(2)-- F输出Shortest distances from A: A: 0 B: 2 D: 1 E: 5 C: 6 F: 7总结Dijkstra 算法是一种重要的图论算法它可以用于解决单源最短路径问题。通过贪心策略和优先队列Dijkstra 算法可以高效地找到从源节点到其他所有节点的最短路径。Dijkstra 算法的核心思想是每次选择当前距离源节点最近的未访问节点然后更新其相邻节点的距离。掌握 Dijkstra 算法的原理和实现对于理解和解决图论相关问题非常重要。