营口市代做网站,网站托管代运营,汕头百度公司,苏州seo培训目录
dijkstra#xff08;堆优化版#xff09;精讲
思路
堆优化细节
方法一#xff1a; 最小堆优化 dijkstra#xff08;堆优化版#xff09;精讲 题目链接#xff1a;卡码网#xff1a;47. 参加科学大会 文章讲解#xff1a;代码随想录 小明是一位科学家#x…目录
dijkstra堆优化版精讲
思路
堆优化细节
方法一 最小堆优化 dijkstra堆优化版精讲 题目链接卡码网47. 参加科学大会 文章讲解代码随想录 小明是一位科学家他需要参加一场重要的国际科学大会以展示自己的最新研究成果。 小明的起点是第一个车站终点是最后一个车站。然而途中的各个车站之间的道路状况、交通拥堵程度以及可能的自然因素如天气变化等不同这些因素都会影响每条路径的通行时间。 小明希望能选择一条花费时间最少的路线以确保他能够尽快到达目的地。 【输入描述】 第一行包含两个正整数第一个正整数 N 表示一共有 N 个公共汽车站第二个正整数 M 表示有 M 条公路。 接下来为 M 行每行包括三个整数S、E 和 V代表了从 S 车站可以单向直达 E 车站并且需要花费 V 单位的时间。 【输出描述】 输出一个整数代表小明从起点到终点所花费的最小时间。 输入示例 7 9
1 2 1
1 3 4
2 3 2
2 4 5
3 4 2
4 5 3
2 6 4
5 7 4
6 7 9输出示例12 【提示信息】 能够到达的情况 如下图所示起始车站为 1 号车站终点车站为 7 号车站绿色路线为最短的路线路线总长度为 12则输出 12。 不能到达的情况 如下图所示当从起始车站不能到达终点车站时则输出 -1。 数据范围 1 N 500; 1 M 5000 思路
堆优化细节
其实思路依然是 dijkstra 三部曲
第一步选源点到哪个节点近且该节点未被访问过第二步该最近节点被标记访问过第三步更新非访问节点到源点的距离即更新minDist数组
只不过之前是 通过遍历节点来遍历边通过两层for循环来寻找距离源点最近节点。 这次我们直接遍历边且通过堆来对边进行排序达到直接选择距离源点最近节点。
先来看一下针对这三部曲如果用 堆来优化。
那么三部曲中的第一步选源点到哪个节点近且该节点未被访问过我们如何选
我们要选择距离源点近的节点即该边的权值最小所以 我们需要一个 小顶堆 来帮我们对边的权值排序每次从小顶堆堆顶 取边就是权值最小的边。
pq中中为什么要存 源点到该节点的权值因为 这个小顶堆需要按照权值来排序
有了小顶堆自动对边的权值排序那我们只需要直接从 堆里取堆顶元素小顶堆中最小的权值在上面就可以取到离源点最近的节点了 未访问过的节点不会加到堆里进行排序
所以三部曲中的第一步我们不用 for循环去遍历直接取堆顶元素
# 1. 第一步选源点到哪个节点近且该节点未被访问过 通过优先级队列来实现
# 节点 源点到该节点的距离
cur_dict,cur_node heapq.heappop(pq)第二步该最近节点被标记访问过 这个就是将 节点做访问标记和 朴素dijkstra 一样 代码如下
# 2. 第二步该最近节点被标记访问过
visited[cur_node] True
cur.first 是指取 pairint, int 里的第一个int即节点编号
第三步更新非访问节点到源点的距离这里的思路 也是 和朴素dijkstra一样的。
但很多录友对这里是最懵的主要是因为两点
没有理解透彻 dijkstra 的思路没有理解 邻接表的表达方式
我们来回顾一下 朴素dijkstra 在这一步的代码和思路如果没看过我讲解的朴素版dijkstra这里会看不懂
# 3、第三步更新非访问节点到源点的距离即更新minDist数组
for j in range(1,n1):if not visited[j] and graph[cur][j] ! float(inf) and graph[cur][j] minDist[cur] minDist[j]:minDist[j] minDist[cur] graph[cur][j]
其中 for循环是用来做什么的 是为了 找到 节点cur 链接指向了哪些节点因为使用邻接矩阵的表达方式 所以把所有节点遍历一遍。
而在邻接表中我们可以以相对高效的方式知道一个节点链接指向哪些节点。
所以在邻接表中我们要获取 节点cur 链接指向哪些节点就是遍历 graph[cur节点编号] 这个链表。
接下来就是更新 非访问节点到源点的距离代码实现和 朴素dijkstra 是一样的代码如下
for edge in edges[cur_node]:if not visited[edge.to] and cur_dict edge.val minDist[edge.to]:minDist[edge.to] cur_dict edge.valheapq.heappush(pq,(minDist[edge.to],edge.to))
方法一 最小堆优化
import heapq
import sys
class Edge:def __init__(self,to,val) - None:self.to to self.val valdef dijkstra(edges,n,start,end):visited [False] * (n1)minDist [float(inf)] * (n1)minDist[start] 0pq []heapq.heappush(pq,(0,start))while pq:cur_dict,cur_node heapq.heappop(pq)if visited[cur_node]:continuevisited[cur_node] Truefor edge in edges[cur_node]:if not visited[edge.to] and cur_dict edge.val minDist[edge.to]:minDist[edge.to] cur_dict edge.valheapq.heappush(pq,(minDist[edge.to],edge.to))return -1 if minDist[end] float(inf) else minDist[end]
if __name____main__:input sys.stdin.readdata input().split()# n个车站m条公路n int(data[0])m int(data[1])edges [[] for i in range(n1)]index 2for i in range(m):start int(data[index])to int(data[index1])val int(data[index2])edges[start].append(Edge(to,val))index 3res dijkstra(edges,n,start1,endn)print(res)
