Python小根堆
# heapq是Python标准库,提供了构建小根堆和大根堆的基本方法
from heapq import heappush, heappop
array = [10, 6, 8, 2, 1, 3] # 初始的无序列表
h = [] # 空列表,待会用于存小根堆
for num in array:
heappush(h, num) # 将数num放入堆中,heappush方法保证放入之后h是小根堆
print(array) # [10, 6, 8, 2, 1, 3]
print(h) # [1, 2, 3, 10, 6, 8] 堆顶元素总是最小
t = heappop(h) # 弹出并返回h中最小的元素,即堆顶元素,同时返回之后又保证了堆的不变性
print(t) # 1
print(h) # [2, 6, 3, 10, 8]
堆优化版本的dijkstra
"""
堆优化版本的Dijkstra算法:用来处理稀疏图问题(点数和边数差不多的情况,稠密图边数大概是点数的平方倍)
先想一下朴素做法:dijkstra是解决单元最短路问题,适用场景是不存在负权边
1.首先初始化所有点到起点的距离为正无穷float("inf"),起点到起点的距离为0
2.总共n个循环,每个循环需要找到不在最短集合中且到起点距离最小的点,把这个点加入到集合当中
3.用刚才找到的点更新所有点到起点的距离
想一想如何优化:
因为每次需要找到到起点距离最小的点,考虑使用小根堆优化,对应Python的heapq
同时因为是稀疏图,就需要用defaultdict来存图
因为输入的时候不处理重边,在堆中可能有冗余,判断一下就行
O(mlogn)
-----------------------------------------------------------
邻接表的模板
from collections import defaultdict
graph = defaultdict(list)
for i in range(n):
x, y, c = map(int, input().split())
graph[x].append([y, c])
"""
from collections import defaultdict
from heapq import heappush, heappop
def dijkstra():
dist[1] = 0 # 初始化起点到起点的距离为0
h = [] # 初始化小根堆
heappush(h, [0, 1]) # 将起点加到堆中
while h:
_, i = heappop(h)
# 如果这个点已经在集合当中了,就不会再更新
if st[i]:
continue
st[i] = True # 否则就找到距离最下的点
# 更新i这个点所有出去的点到起点的距离
for item in graph[i]:
j, distance = item
if dist[j] > dist[i] + distance:
dist[j] = dist[i] + distance
heappush(h, [dist[j], j])
if dist[n] == float("inf"):
return -1
return dist[n]
n, m = map(int, input().strip().split())
graph = defaultdict(list) # 邻接表
for i in range(m):
a, b, c = map(int, input().strip().split())
graph[a].append([b, c])
# print(graph)
dist = [float("inf") for _ in range(1+n)] # 初始化所有点到起点的距离为无穷大
st = [False for _ in range(n+1)] # 判断每个点是不是已经在集合当中了
print(dijkstra())