目录
前置知识：堆数据结构-堆-CSDN博客
背景
还记得BFS中是逐层拓展的吗，那么首先到达k点的一定是该层中离k最近的
但是BFS拓展过程中每层的间隔是一样的
现在我们要处理更一般的问题：如果边权（路径代价不同）不一样怎么办？
这就用到了我们的Dijkstra算法- 带权重的BFS
这是一种“单源”最短路径算法（无法处理负权），一次计算能得到一个起点s到其他所有点的最短路径
一般来说有：Dijkstra = BFS + 优先队列
不同于普通BFS“谁先进队就先处理谁”，Dijkstra算法是贪心：优先处理当前代价最小的点（因为按照当前最小代价出队的时候它的最短路径就被确定了）
实现
heapq和PriorityQueue两种方法都可以（但是只有heapq在标准库里）
def dijkstra(e, s):
"""
输入：
e:邻接表
s:起点
返回：
dis:从s到每个顶点的最短路长度
"""
dis = defaultdict(lambda: float("inf"))
dis[s] = 0
q = [(0, s)]
vis = set()
while q:
_, u = heapq.heappop(q)
if u in vis:
continue
vis.add(u)
for v, w in e[u]:
if dis[v] > dis[u] + w:
dis[v] = dis[u] + w
heapq.heappush(q, (dis[v], v))
return dis堆中每个元素是（步数，位置）
dis中存储了从起点到各点的距离
对于每一个（当前步数，当前位置u）：
先记忆性：如果已经访问过u（已经走过的那肯定是前面走的时候更短），那么就下一个邻居
遍历邻接列表【当前位置u】：#遍历u的能到的地方v
如果从起点先到u，再从u到v 要小于 直接从s到v：
那么更新dis【v】
并且往堆中添加（到v的代价，v） #找到一个更短路径了，后面再次处理
过程
我们将节点分为两个集合，这就是我们Dijstra算法主要维护的对象：一个集合存储已确定最短路长度的所有点（记为S）；另一个集合存储未确定最短路长度的所有点（记为T）
那么一开始所有点都在 T 中
初始化 dis(s)=0 ，其他点的 dis 均为无穷大（未到达）
下面我们要循环两个操作：（直到所有点都到 S 集合中，也就是确定最短路，再结束）
1. 从 T 集合中选取一个最短路长度最小的节点，移到 S 集合中
2. 对那些刚被加入 S 集合的节点的所有出边执行松弛操作