代码随想录算法训练营第五十九天 | dijkstra（堆优化版）精讲

目录

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 三部曲：

1. 第一步，选源点到哪个节点近且该节点未被访问过
2. 第二步，该最近节点被标记访问过
3. 第三步，更新非访问节点到源点的距离（即更新minDist数组）

只不过之前是 通过遍历节点来遍历边，通过两层for循环来寻找距离源点最近节点。 这次我们直接遍历边，且通过堆来对边进行排序，达到直接选择距离源点最近节点。

先来看一下针对这三部曲，如果用 堆来优化。

那么三部曲中的第一步（选源点到哪个节点近且该节点未被访问过），我们如何选？

我们要选择距离源点近的节点（即：该边的权值最小），所以 我们需要一个 小顶堆 来帮我们对边的权值排序，每次从小顶堆堆顶 取边就是权值最小的边。

（pq中中为什么要存 源点到该节点的权值，因为 这个小顶堆需要按照权值来排序）

有了小顶堆自动对边的权值排序，那我们只需要直接从 堆里取堆顶元素（小顶堆中，最小的权值在上面），就可以取到离源点最近的节点了 （未访问过的节点，不会加到堆里进行排序）

所以三部曲中的第一步，我们不用 for循环去遍历，直接取堆顶元素：

# 1. 第一步，选源点到哪个节点近且该节点未被访问过 （通过优先级队列来实现）
# 节点， 源点到该节点的距离
cur_dict,cur_node = heapq.heappop(pq)

第二步（该最近节点被标记访问过） 这个就是将 节点做访问标记，和 朴素dijkstra 一样 ，代码如下：

# 2. 第二步，该最近节点被标记访问过
visited[cur_node] = True

（cur.first 是指取 pair<int, int> 里的第一个int，即节点编号 ）

第三步（更新非访问节点到源点的距离），这里的思路 也是 和朴素dijkstra一样的。

但很多录友对这里是最懵的，主要是因为两点：

• 没有理解透彻 dijkstra 的思路
• 没有理解 邻接表的表达方式

我们来回顾一下 朴素dijkstra 在这一步的代码和思路（如果没看过我讲解的朴素版dijkstra，这里会看不懂）

# 3、第三步，更新非访问节点到源点的距离（即更新minDist数组）
for j in range(1,n+1):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] * (n+1)minDist = [float('inf')] * (n+1)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(n+1)]index = 2for i in range(m):start = int(data[index])to = int(data[index+1])val = int(data[index+2])edges[start].append(Edge(to,val))index += 3res = dijkstra(edges,n,start=1,end=n)print(res)