网站的基本类型,cpa广告联盟平台,创新产品设计,国内常用的crm系统前言#xff1a;
Dijkstra算法博客讲解分为两篇讲解#xff0c;这两篇博客对所有有难点的问题都会讲解#xff0c;小白也能很好理解。看完这两篇博客后保证收获满满。
第一篇博客讲解朴素Dijkstra算法Dijkstra求最短路篇一(全网最详细讲解两种方法#xff0c;适合小白)(p…前言
Dijkstra算法博客讲解分为两篇讲解这两篇博客对所有有难点的问题都会讲解小白也能很好理解。看完这两篇博客后保证收获满满。
第一篇博客讲解朴素Dijkstra算法Dijkstra求最短路篇一(全网最详细讲解两种方法适合小白)(python其他语言也适用)本篇博客讲解堆优化Dijkstra算法两中算法思路大体相同但时间复杂度有所区别。
朴素Dijkstra算法时间复杂度 O ( n 2 ) O(n^2) O(n2)堆优化Dijkstra算法时间复杂度 O ( m l o g n ) O(mlogn) O(mlogn)
两篇博客给出的题目内容一样只有数据规模不一样。
题目
题目链接 850. Dijkstra求最短路 II
给定一个 n 个点 m 条边的有向图图中可能存在重边和自环所有边权均为非负值。请你求出 1 号点到 n 号点的最短距离如果无法从 1 号点走到 n 号点则输出 −1。
输入格式 第一行包含整数 n 和 m。 接下来 m 行每行包含三个整数 x,y,z表示存在一条从点 x 到点 y 的有向边边长为 z。
输出格式 输出一个整数表示 1 号点到 n 号点的最短距离。 如果路径不存在则输出 −1。
数据范围两题不同处 1 ≤ n , m ≤ 1.5 × 1 0 5 1≤n,m≤1.5×10^5 1≤n,m≤1.5×105, 图中涉及边长均不小于 0且不超过 10000。 数据保证如果最短路存在则最短路的长度不超过 1 0 9 10^9 109。
输入样例 3 3 1 2 2 2 3 1 1 3 4 输出样例 3 思路
算法分析
依旧是Dijkstra算法求解不同的是本题需要降低时间复杂度。
对朴素Dijkstra算法时间复杂度分析可知
寻找路径最短的点 O ( n 2 ) O(n^2) O(n2)加入集合S O ( n ) O(n) O(n)更新距离 O ( m ) O(m) O(m)所以总的时间复杂度为 O ( n 2 ) O(n^2) O(n2)
所以我们需要对寻找路径最短的点进行改变如何降低找最短距离的点的时间复杂度呢 这里可以使用最小堆进行优化也就是优先队列对优先队列不太熟悉的可以看看优先队列这篇博客其他博主写的很详细这里我就不介绍了。
进行优化后时间复杂度分析如下
寻找路径最短的点 O ( n ) O(n) O(n)加入集合S O ( n ) O(n) O(n)更新距离 O ( m l o g n ) O(mlogn) O(mlogn)
堆的数据结构大家接触的可能有点少python中有专门的库函数可以直接使用其他语言也有类似的库函数可以使用。
构造邻接表
首先对数据进行存储图的存储有两种方式一种是邻接表一种是邻接矩阵。题目中的数据规模用邻接表存储本题数据规模是稀疏图。
为什么要用邻接表去存贮而不是邻接矩阵
我们采用邻接矩阵还是采用邻接表来表示图需要判断一个图是稀疏图还是稠密图。稠密图指的是边的条数|E|接近于|V|²稀疏图是指边的条数|E|远小于于|V|²数量级差很多。本题是稠密图显然稠密图用邻接矩阵存储比较节省空间反之用邻接表存储。
邻接表存储就不需要注意重边和自环了因为算法会自动算出最优解
邻接矩阵存储代码如下
n, m map(int, input().split()) # 图的节点个数和边数
# 构建邻接表
num [[] for i in range(n 1)]
for _ in range(m):a, b, c map(int, input().split())num[a].append((b, c)) # 无需考虑重边和自环以题目实例为例打印num数组
[[], [(2, 2), (3, 4)], [(3, 1)], []]邻接表构建完成之后就要进行Dijkstra算法这里直接给出代码用详细代码给大家进行讲解。整体思路跟朴素Dijkstra算法大致相同
代码及详细注释
import heapqn, m map(int, input().split()) # 图的节点个数和边数
# 构建邻接表
num [[] for i in range(n 1)]
for _ in range(m):a, b, c map(int, input().split())num[a].append((b, c)) # 无需考虑重边和自环
dist [float(inf) for _ in range(n 1)] # float(inf)在python中是无限大的意思
dist[1] 0 # 源点到源点的距离为置为 0
state [False for i in range(n 1)] # state 用于记录该点的最短距离是否已经确定def dijstra():# 这里heap中为什么要存两个值呢首先小根堆是根据距离来排的所以有一个变量要是距离# 其次在从堆中拿出来的时候要知道知道这个点是哪个点不然怎么更新邻接点呢所以第二个变量要存点。heap [(0, 1)] # 首先放入距离0和点1这个顺序不能倒这里显然要根据距离排序while heap:distance, i heapq.heappop(heap) # 这里是取出最下距离和对应的点最小堆自动取出最小值if state[i]: # 如果该点最短距离已经确定跳过下面操作continuestate[i] True # 标记该点距离确定for j, d in num[i]: # 循环遍历找点i所能到的点和其距离if dist[j] distance d: # 如果原本点j到源点的距离大于后续计算出来的值dist[j] distance d # 更新heapq.heappush(heap, (dist[j], j)) # 该点距离和点加入到最小堆中# 判断最后一个点的最短距离是否找到如果为无穷大则表示未找到返回-1否则返回最短距离dist[-1]if dist[n] float(inf):return -1else:return dist[n]print(dijstra())
朴素Dijkstra算法大家理解好了本算法也很好理解操作都是一样只是在寻找路径最短的点时用了最小堆操作。这里就不拿实例带大家过了如果略微有点懵大家可以自己拿实例数据过一遍。
本题主要对 Python 中的 heapq 库进行简略讲解。
import heapqheap []
heapq.heappush(heap, (1, 2))
heapq.heappush(heap, (1, 3))
heapq.heappush(heap, (2, 1))
heapq.heappush(heap, (2, 0))
heapq.heappush(heap, (0, 2))
heapq.heappush(heap, (0, 0))print(初始状态, heap)
print(删除的元素, heapq.heappop(heap))
print(删除后状态, heap)
运行结果
初始状态 [(0, 0), (1, 2), (0, 2), (2, 0), (1, 3), (2, 1)]
删除的元素 (0, 0)
删除后状态 [(0, 2), (1, 2), (2, 1), (2, 0), (1, 3)]heapq.heappush(heap, (1, 2)把元素12加入到堆 heap中每次加入后都是最小堆的构建形式。heapq.heappop(heap)弹出堆顶元素最小堆的堆顶就是最小元素。
总结
堆优化版dijkstra适合稀疏图
思路 堆优化版的dijkstra是对朴素版dijkstra进行了优化在朴素版dijkstra中时间复杂度最高的寻找距离 最短的点O(n^2)可以使用最小堆优化。 一号点的距离初始化为零其他点初始化成无穷大。将一号点放入堆中。不断循环直到堆空。每一次循环中执行的操作为 弹出堆顶与朴素版diijkstra找到S外距离最短的点相同并标记该点的最短路径已经确定。 用该点更新临界点的距离若更新成功就加入到堆中。 时间复杂度分析
寻找路径最短的点 O ( n ) O(n) O(n)加入集合S O ( n ) O(n) O(n)更新距离 O ( m l o g n ) O(mlogn) O(mlogn)
