Dijkstra算法优化~~你一定可以看懂的四种进阶优化

注：博主已经发表过一篇Dijkstra的算法讲解， 若读者不会此算法的基础版本，还请读者先自行翻阅我的博客，学会Dijkstra算法再看这篇。若有疑问可以私信我或在评论区留言，愿能帮助到你。

我们试想一下，在顶点很多的无向图中，边却很少，如果我们还是利用邻接矩阵来实现图的存储的话那么我们会做很多无用功，这样是我们不愿看到的，那么我们如果可以存储边来抽象表示我们的无向图，那岂不是美滋滋，因为我们只需要对较少的边进行运算即可。这里我们会介绍两种方法：1、链式前向星存储；2、vector实现邻接表。

使用这种优化的前提就是：实际边远小于无向图的最大边数。

在说链式前向星之前我们先了解前向星，前向星是一种数据结构，以存储边的方式来存储图。构造方法如下：读入每条边的信息，将边存放在数组中，把数组中的边按照起点顺序排序，前向星就构造完了。通常用在点的数目太多，或两点之间有多条弧的时候。一般在别的数据结构不能使用的时候才考虑用前向星。除了不能直接用起点终点定位以外，前向星几乎是完美的。

这种方法有种弊端，就是边与边的关系没有联立起来，尤其在我们的Dijkstra算法中就是根据同一点的边进行拓展的，所以在这基础上我们推出了链式前向星，这种就可以根据起点来进行组合，形成跟邻接表一样的效果，但比邻接表要简单的多。我们来看下这是怎么联立的，代码附了详细解释。

这个核心就是利用head数组和边集合中的next来联立的，第一条边的上一条边永远是-1，这在之后整个的代码实现中会看到。我们存储好边之后，就可以开始我们的关键Dijkstra算法的实现了，还是以贪心的思想去实现，我们来看代码。

这种和邻接表一样的思想，但实现起来比链式存储的要简单的多，相当于是N个边数组。我们来看存储结构的实现

没错，你没看错，就是这么简单，这graph[i]对应的就是以起点为i的边向量，那么若起点i没有边，则该向量自然为空，这比链式前向星要更好理解。下面看整个的实现吧，核心几乎没变，因为都是对边进行操作，如果你领悟了上一种，这种也自然可以解决了。

我们发现在Dijkstra算法中，总是要寻找当前的最短的最短路径，这是需要时间来查找的，但如果我们利用优先队列的自动排序的功能，即用堆实现这个功能，在每一趟中选择队头元素，这就是我们想要的最短路径的相关信息，也就是这样我们就可以不用去查找了，我们接下来介绍我们的这两种优化：1、链式前向星优化。2、vector邻接表优化。是基于第五种来的，也是最终版本。

非常重要的一点就是，我们把所有更新好了的最短路径全部加入队列中，这是没问题的，因为如果有个点已经确定了最短路径，那么这条语句就会发挥作用：每次取出来的都是目前最短的最短路径信息。同样，也是因为这条语句，当所有点确定完之后自然会导致队空。只要了解了优先队列，了解了第五种优化，那么这种超级优化读者应该可以看懂的。

PS：对于pair类型，优先队列会先比较第一个的值，若相等，再判断第二个的值。