2023年7月30日发(作者：)

Dijkstra和堆优化Dijkstra算法由于我之前⼀直记的迪杰斯特拉的翻译导致我把dijkstra写成了dijstra……所以下⽂#define dijstra dijkstra我以后叫她迪杰克斯歘！Dijskra是⽤来在有向图或者⽆向图中寻找任意两个点的最⼩距离的算法。它相较于spfa不会死掉（spfa死了），但是⽆法处理带负环的图和求最长路（除⾮加上⼀些奇怪的东西，我们这⾥是新⼿村不予讨论我不会）Dijskra的核⼼思想是先把所有边的边权进⾏从⼩到⼤的排序，再建⼀个记录起点到各个点的距离的dis数组并初始化其为⼀个最⼤值(inf=!0U>>1,或者0x3f3f3f3f什么的，但不要⾃⼰觉得很⼤但是⼩了。注意，要把到起点的距离dis[start]设为0)，每次讨论⼀个点i遍历所有和它相连的边到的点j，如果起点到i的距离加上边权⼩于顶点到j的距离，那么更新j的距离。然后再选⼀个最近的点标记⼀下vis，再次进⾏遍历。处理完之后得到dis[end]就是起点到终点的距离了。⾄于dijskra的推导和证明，我不会我们在这⾥不予讨论。还是不懂的话可以搜⼀搜其他⼊门帖⼦（有图的那种）存图的话，可以⽤邻接矩阵和前向星。Dijskra的堆优化我们发现，每次遍历⼀个点就需要把所有的边都扫⼀遍然后进⾏松弛。这个导致朴素dijskra⾮常慢。所以我们可以想个法⼦优化⼀下。就是——使⽤⼩根堆。我们可以发扬C++的伟⼤之处，⽤priority_queue和pair进⾏优化。讲解⼀下pair关键字。它在C++的（发⾳[juˈtɪlətɪ]）头⽂件中。简单来说就是⼀个只有两个元素的结构体。加⼊我们定义了⼀个pair p;的pair，那么我们可以⽤和来分别调⽤他的两个元素。pair有什么好处呢？当我们使⽤sort的时候，它会先根据第⼀关键字进⾏排列，当第⼀关键词相同时再根据第⼆关键字排列。所以我们⽤pair存边的时候，⽤first存边权，⽤second存编号即可。make_pair(a,b)关键字可以把a和b弄成⼀个pair。这在我们要把⼀个pair放进优先队列时有⽤。我们再来看看优先队列的部分。裸的优先队列是⼤根堆（从⼤到⼩），我们需要把它重新定义⼀下变成⼩根堆，即：priority_queue,greater >q;greater操作符就是重载运算符()变成了(>)。less和它相反。它们在头⽂件⾥。记得引⽤。（似乎algorithm已经包含了）所以我们就可以轻松得到优化后的代码~typedef pair pii;int dis[maxn];bool vis[maxn];inline void dijkstra(int start,int end){ memset(dis,0x3f3f3f3f,sizeof dis); priority_queue,greater > q; (make_pair(0,start)),dis[start]=0; while(!()) { int u=().second;(); if(vis[u])continue; vis[u]=1; for(int i=head[u];i;i=nxt[i]) { int v=t[i],w=val[i]; if(dis[v]>=dis[u]+w) { dis[v]=dis[u]+w; (make_pair(dis[v],v)); } } }}（update：之前没有加⼊vis数组是因为我认为它没有影响，抱歉。）