Dijkstra+堆优化+链式前向星
使用链式前向星优化Dijkstra
使用链式前向星主要是对Dijkstra进行了空间上的优化,例如,如果有10000个点,100000条边,这样是无法用邻接矩阵存图的。只能使用邻接表的方式。时间上应该也有一定的优化。不过只是对松弛操作
进行了优化,所以效果不是很明显。这时候,我们就可以使用优先队列进行时间的优化。
我们都知道,在Dijkstra的松弛操作中,其实只有当前离起点最近的点可能会对其他点进行松弛,所以,我们开一个优先队列,头部放离起点最近的点即可。
另外,之前松弛过的点是不可能再对其他点进行松弛的,所以标记一下用过的点,下次遇到直接跳过
一点题外话:结构体<
运算符的重载操作:
1 | struct node |
Dijkstra
+堆优化
+链式前向星
模板代码:
1 | ll head[1010]; |