算法导论——Dijkstra

各位久等了!算法导论复活了 虽说有了洛谷日报,我这也没啥用了

咳咳,不说废话,直接进入主题!

$Dijkstra$是单源最短路的一种算法(以下简称$Dij$),其本质是贪心,因此不能解决负边权问题(叹气)

具体思路如下:

  1. 定义变量:$s$起点,$dis[i]$表示起点到$i$的最短距离,$map[i][j]$表示边$i,j$的权值,$vis[i]$表示$i$是否被访问

  2. 将$map[i][j]$初始化为$INF$,$map[i][i]=0$

  3. 读入,并加边

  4. $dis[s]=0$,将$dis$更新一遍(不可到达点为$INF$)

  5. 找到距初始点最近的未访问点$t$,记录为访问

  6. 松弛(以$t$为中间点):$dis[i]=\min(dis[i],dis[t]+map[t][i])$

  7. 重复$n$遍步骤$5$

  8. 输出答案即可

可以看出,$Dij$的时间复杂度是$O(n^2)$,理论上慢于$SPFA$,至于实际嘛……

对于菊花图这类恶心的卡$SPFA$的图,$Dij$可以轻松跑过,不过对于P4779还是远远不够的!

下面,进阶操作来了:

$Dij$的堆优化!!!

观察步骤$5$,发现查找这一点可以利用堆维护$dis$数组,每次取出堆顶即可

有同学发问了:可是这样就不能判断是否未访问了

不错,但我们可以不停地把堆顶访问过的删掉,直到堆顶是未访问过的

有同学又发问了:可是这样会有重复节点啊!

很好,接下来我们需要引入一个概念:懒惰删除

这是指不删除节点,而直接跳过该节点的操作

例如:堆中有点$(1,2),(1,3),(2,3)$

此时$dis[1]=2,dis[2]=3$

在第二次操作时,会发现$dis[1]!=3$,那么,我们就懒惰删除,跳过它!

至于堆的实现,可以使用$STL$的$priority$_$queue$来代替
(您如果想手写堆,我也不拦着您)

注:这题不能用邻接矩阵!!!要用链式前向星(参见$SPFA$

复杂度分析:对于每个点,删除,插入,取出操作均为$\log n$,每条边也是$\log n$,因此总复杂度为$O((n+m)\log n)$

所以计算一下:最坏情况约为$5000000$左右,建议加个快读,不然……

这样就能$AC P4779$了!

代码实现:

参见P4779题解(个人建议第二篇)

0%