我觉得是时候该写写最短路了...

翻了翻我在CSDN写的dij,都是啥玩意,居然扯上了并查集。。不知道当时我咋想的。

那么这篇博客就来讲讲这个叫迪杰斯特拉的最短路算法吧。

它应该是最短路算法中最常见的,floyd太慢,SPFA褒贬不一,而dij除了不能处理负环回路,其他地方都能体现它是很好的最短路算法。

为什么要把这两个算法串起来呢?它们实在是太像了。以至于改动$Prim$模板的一行代码就能成为$dijkstra$的模板。

它和prim一样,都用了类似于贪心的思想,把所有点分为走过了和没走过,每次就找到和当前点相连并且没走过,和当前点权值最短的来走。

既然有分点,那就需要打标记(代码中有体现)。

贴下标准的最短路的模板代码(朴素dij):

CODE

但是由于朴素的dij每次寻找和自己相连并且相连权值最短的点的时候,都要花费O(与自己相连的点数)的时间(其实就是用vector+for循环过一遍),导致朴素dij的时间复杂度达到了惊人的$O(n^2)$。

所以我们需要对取最短边权的对应点这一步进行优化。

首先我们要看清这一步的实质,实际上就是在找最值(最小边权)

快速查询一个数值集合里面的最值的数据结构有啥?堆啊!

只要对于每个点,把和他连着的点以及权值来建立一个堆,$O(log2(n))$的时间来负责取出堆顶元素并删除,$O(log2(m))$的时间来遍历每一条边,总时间复杂度$O((n+m)×log2(n))$,已经达到了一个较快的速度,是一个优秀的最短路算法了

模板题【只能用堆优化dij才能AC】

代码实现如果不会建议先去学堆,摸鱼酱要在这里说一声真香当初信誓旦旦说STL太慢现在用起来很爽

要想快的话就去学优先队列+重载运算符就行。

代码一样贴下面:

code

ov.

最后修改:2020 年 03 月 15 日 04 : 03 PM