企业官网建设流程全解析

LeetCode Dijkstra 算法题解

题目描述

Dijkstra 算法是一种用于解决单源最短路径问题的贪心算法。它可以在加权图中找到从源节点到其他所有节点的最短路径，前提是边的权重都是非负的。

示例：

对于以下加权图：

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

从 A 出发到各节点的最短路径长度为：

• A → D: 1
• A → B: 2
• A → E: 1+5=6 或 A→B→E: 2+3=5（更短）
• A → C: 2+4=6
• A → F: 2+3+2=7 或 A→B→C→F: 2+4+1=7

解题思路

方法：Dijkstra 算法

思路：

• Dijkstra 算法的核心思想是使用贪心策略，每次选择当前距离源节点最近的未访问节点，然后更新其相邻节点的距离。
• 具体步骤：
  1. 初始化一个距离数组，源节点的距离为 0，其他节点的距离为无穷大。
  2. 使用优先队列（最小堆）来存储未访问的节点及其距离。
  3. 从源节点开始，每次从优先队列中取出距离最小的节点，标记为已访问。
  4. 对于该节点的每个相邻节点，计算通过当前节点到达该相邻节点的距离，如果这个距离比已知的距离小，则更新距离并将相邻节点加入优先队列。
  5. 重复步骤 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 算法的原理和实现，对于理解和解决图论相关问题非常重要。