算法导论——Dijkstra

各位久等了！算法导论复活了 ~~虽说有了洛谷日报，我这也没啥用了~~ 咳咳，不说废话，直接进入主题！ $Dijkstra$是单源最短路的一种算法（以下简称$Dij$），其本质是**贪心**，因此**不能解决负边权**问题（叹气） 具体思路如下： 1. 定义变量：$s$起点，$dis[i]$表示起点到$i$的最短距离,$map[i][j]$表示边$i,j$的权值，$vis[i]$表示$i$是否被访问 1. 将$map[i][j]$初始化为$INF$，$map[i][i]=0$ 1. 读入，并加边 1. $dis[s]=0$，将$dis$更新一遍（不可到达点为$INF$） 1. 找到距**初始点**最近的**未访问**点$t$，记录为访问 1. **松弛**（以$t$为中间点）：$dis[i]=\min(dis[i],dis[t]+map[t][i])$ 1. 重复$n$遍步骤$5$ 1. 输出答案即可 可以看出，$Dij$的时间复杂度是$O(n^2)$，理论上慢于$SPFA$，至于实际嘛…… 对于**菊花图**这类恶心的卡$SPFA$的图，$Dij$可以轻松跑过，不过对于[P4779](https://www.luogu.org/problem/P4779)还是远远不够的！ 下面，进阶操作来了： **$Dij$的堆优化**！！！ 观察步骤$5$，发现查找这一点可以利用**堆维护$dis$数组**，每次取出堆顶即可 有同学发问了：可是这样就不能判断**是否未访问了**！ 不错，但我们可以不停地把堆顶访问过的删掉，直到堆顶是未访问过的 有同学又发问了：可是这样会有重复节点啊！ 很好，接下来我们需要引入一个概念：**懒惰删除** 这是指不删除节点，而直接跳过该节点的操作 例如：堆中有点$(1,2),(1,3),(2,3)$ 此时$dis[1]=2,dis[2]=3$ 在第二次操作时，会发现$dis[1]!=3$，那么，我们就**懒惰删除**，跳过它！ 至于堆的实现，可以使用$STL$的$priority\_queue$来代替 ~~（您如果想手写堆，我也不拦着您）~~ （本人代码使用平板电视的$priority\_queue$） 注：这题不能用邻接矩阵！！！要用链式前向星（参见[$SPFA$](https://www.luogu.org/blog/Victory-Defeat/suan-fa-dao-lun-spfa)） 复杂度分析：对于每个点，删除，插入，取出操作均为$\log n$，每条边也是$\log n$，因此总复杂度为$O((n+m)\log n)$ 所以计算一下：最坏情况约为$5000000$左右，建议加个快读，不然…… 这样就能$AC\ P4779$了！ 代码实现： ```cpp #include<iostream> #include<cstdio> #include<vector> #include<ext/pb_ds/priority_queue.hpp> using namespace std; using namespace __gnu_pbds; struct edge { int node,weight; edge(int node_,int weight_): node(node_),weight(weight_){} }; vector<edge>v[100001]; int n,m,s,dis[100001]; bool vis[100001]; inline void dijkstra() { __gnu_pbds::priority_queue<pair<int,int>,greater<pair<int,int> >,pairing_heap_tag>q; q.push(make_pair(0,s)); while(!q.empty()) { pair<int,int>k=q.top(); q.pop(); if(vis[k.second])continue; vis[k.second]=1; dis[k.second]=k.first; for(auto it=v[k.second].begin();it!=v[k.second].end();++it) q.push(make_pair(it->weight+k.first,it->node)); } } int main() { scanf("%d%d%d",&n,&m,&s); for(int i=1;i<=m;++i) { int x,y,w; scanf("%d%d%d",&x,&y,&w); v[x].push_back(edge(y,w)); } dijkstra(); for(int i=1;i<=n;++i)printf("%d ",dis[i]); putchar('\n'); return 0; } ```