算法导论——Dijkstra

发表于 阅读次数：
本文字数： 932 阅读时长 ≈ 1 分钟

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

咳咳，不说废话，直接进入主题！

$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%