核心内容摘要
linux学习笔记（磁盘管理）
Dijkstra算法的堆优化版本是针对其朴素算法效率不足的改进特别适用于稀疏图边数远小于顶点数平方的图。
下面我将从算法思想和代码实现两方面进行解释。
算法思想Dijkstra算法用于求解单源最短路径问题即从给定的起点出发计算其到图中所有其他顶点的最短路径。
它的核心是贪心策略基本步骤如下初始化将起点到自身的距离设为0到其他所有顶点的距离初始化为无穷大。
选择未访问最近节点从所有尚未确定最短路径的顶点中选出当前距离起点最近的一个。
松弛操作对于刚选出的这个顶点的所有邻居检查是否存在一条通过当前顶点到达该邻居的更短路径。
如果有则更新该邻居顶点的最短距离。
标记已访问将当前顶点标记为已处理其最短距离已确定。
重复重复步骤
直到所有顶点都被处理完毕。
在朴素Dijkstra算法中步骤2“选择未访问最近节点”是通过遍历所有未访问节点来实现的这使得其时间复杂度为O(n²)。
当顶点数量n很大时效率较低。
堆优化的核心思想在于使用一个最小堆优先队列 来维护所有当前“距离起点距离已知但尚未最终确定”的顶点。
堆顶元素始终是当前距离最小的顶点。
这样步骤2中获取最小距离节点的操作时间复杂度可以从O(n)降低到O(
获取堆顶而每次调整堆插入或删除的时间复杂度为O(log n)从而将算法的整体时间复杂度优化到O((n m) log n)其中m是边的数量。
代码实现解析import heapq class Edge: def __init__(self, to, val): self.to to # 这条边指向的顶点 self.val val # 边的权重 def dijkstra(n, m, edges, start, end): #
图的构建使用邻接表 grid [[] for _ in range(n
] for p1, p2, val in edges: grid[p1].append(Edge(p2, val)) # 存储从p1出发到p2的边 #
初始化数据结构 minDist [float(inf)] * (n
# 记录起点到每个顶点的最短距离估计值 visited [False] * (n
# 标记顶点是否已确定最短距离 pq [] # 最小堆优先队列 # 起点初始化 minDist[start] 0 heapq.heappush(pq, (0, start)) # 将起点(距离0, 顶点编号)入堆 #
主循环 while pq: #
1 取出当前距离起点最近的未访问顶点 cur_dist, cur_node heapq.heappop(pq) # 关键优化如果该顶点已被处理过则跳过由于堆中可能存在同一顶点的多个历史距离 if visited[cur_node]: continue # 标记当前顶点为已访问此时cur_dist就是它的最终最短距离 visited[cur_node] True #
2 松弛操作遍历当前顶点的所有邻居 for edge in grid[cur_node]: # 如果邻居未被访问且通过当前顶点到达邻居的距离更短 if not visited[edge.to] and cur_dist edge.val minDist[edge.to]: # 更新邻居的最短距离估计值 minDist[edge.to] cur_dist edge.val # 将新的距离和邻居顶点入堆。
注意这里入堆的是新的估计值旧的估计值依然在堆中但会被上面的continue跳过。
heapq.heappush(pq, (minDist[edge.to], edge.to)) # 返回起点到终点的最短距离若不可达则返回-1 return -1 if minDist[end] float(inf) else minDist[end]核心要点与优化解释邻接表 (grid)使用邻接表而非邻接矩阵来存储图特别适合边数较少的稀疏图节省空间。
最小堆 (pq)heapq模块实现了最小堆。
堆中的元素是元组(distance, node)。
Python比较元组时按顺序比较因此以距离作为第一项能保证堆总是按距离从小到大排序。
visited数组的重要性这是避免重复处理的关键。
当一个顶点从堆中弹出时如果它已经被标记为visited说明有更短的路径已经确定了它的距离当前弹出的这个可能更大的距离记录就是无效的直接跳过。
冗余入堆代码中在更新一个邻居的距离后会直接将其新距离入堆而不是先删除堆中该邻居的旧距离。
这会导致堆中可能存在同一个顶点的多个不同距离记录。
这是一种常见的“惰性删除”优化虽然增加了堆的大小但避免了复杂的堆内元素修改操作在实践中通常更高效。
最终的正确性由visited数组和出堆时的检查来保证。
Bellman-Ford 算法是解决带负权边的有向图单源最短路径问题的一种经典算法。
下面我将结合你提供的代码详细解释其原理和实现。
⚙️ 算法核心思想Bellman-Ford 算法通过动态规划和松弛操作来求解最短路径。
其核心步骤是进行最多V-1轮V 为顶点数的松弛操作确保找到从源点到所有其他顶点的最短路径。
如果图中存在从源点可达的负权环算法能够检测出来。
关键特性处理负权边与 Dijkstra 算法不同Bellman-Ford 允许图中包含负权重的边。
检测负权环通过额外的松弛操作可以判断图中是否存在负权环。
简单路径限制最短路径最多包含V-1条边因此最多需要V-1轮松弛。
算法流程与代码解析以下流程图展示了 Bellman-Ford 算法的主要步骤和你代码中的关键逻辑对应你提供的代码其执行过程如下
初始化距离数组minDist [float(inf)] * (n
# 所有顶点初始距离为无穷大 minDist[1] 0 # 源点起点距离设为0创建一个数组minDist用于记录从源点顶点1到各个顶点的当前最短距离估计值。
初始时源点自身的距离设为0其他顶点设为无穷大表示尚未找到路径。
核心松弛操作for i in range(1, n): # 最多进行n-1轮松弛 updated False for src, dest, weight in edges: # 遍历所有边 if minDist[src] ! float(inf) and minDist[src] weight minDist[dest]: minDist[dest] minDist[src] weight # 松弛操作 updated True if not updated: # 提前终止优化 break外层循环最多进行n-1轮。
因为任何不含负权环的最短路径最多包含n-1条边。
内层循环遍历图中的所有边。
对于每条边(src, dest, weight)进行松弛操作检查如果从源点经过顶点src再到顶点dest的路径距离比当前已知到dest的最短距离更短则更新minDist[dest]。
提前终止优化如果在一轮松弛中没有任何距离被更新说明所有最短路径已被找到可以提前结束循环减少不必要的计算。
结果返回if minDist[-1] float(inf): # 检查终点是否可达 return unconnected return minDist[-1] # 返回到达终点的最短距离检查目标顶点通常是编号为n的顶点的最短距离是否仍是无穷大。
如果是则表示从源点无法到达该顶点返回 unconnected。
否则返回计算得到的最短距离。
关键点说明
负权环处理代码没有显式检测负权环。
标准的 Bellman-Ford 算法在完成n-1轮松弛后会再进行一轮松弛。
如果在这一轮中任何顶点的距离还能被更新则说明图中存在从源点可达的负权环因为可以不断绕环降低总路径成本。
添加检测的代码如下# 在n-1轮松弛之后添加负权环检测 for src, dest, weight in edges: if minDist[src] ! float(inf) and minDist[src] weight minDist[dest]: return 图中存在从源点可达的负权环无最短路径在你的代码中由于题目可能确保无负权环或者只关心连通性因此省略了此步骤。
时间复杂度与空间复杂度时间复杂度代码中有两层循环外层最多n-1次内层遍历所有m条边因此最坏时间复杂度为 O(nm)*。
空间复杂度主要是存储边集和距离数组空间复杂度为 O(n m)