朴素Dijkstra与堆优化Dijkstra总结，初学算法如有错误还望指正。
Dijkstra
朴素版dijkstra适合稠密图
思路
集合S为已经确定最短路径的点集。
1. 初始化距离
一号结点的距离为零，其他结点的距离设为无穷大（看具体的题）。
2. 循环n次，每一次将集合S之外距离最短X的点加入到S中去（这里的距离最短指的是距离1号点最近。
点X的路径一定最短，基于贪心，严格证明待看）。然后用点X更新X邻接点的距离。
时间复杂度分析
寻找路径最短的点：$O(n^2)$
加入集合S：$O(n)$
更新距离：$O(m)$
所以总的时间复杂度为$O(n^2)$
具体问题
稠密图用邻接矩阵存。
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N = 510, M = 100010;
int g[N][N], dist[N];
bool visited[N];
int n, m;
int dijkstra()
{
memset(dist, 0x3f, sizeof(dist));
dist[1] = 0;
for(int i = 1; i <= n; i++)
{
int t = -1;
for(int j = 1; j <= n; j++)
{
if(!visited[j] && (t == -1 || dist[j] < dist[t]))
t = j;
}
visited[t] = true;
for(int j = 1; j <= n; j++)
dist[j] = min(dist[j], dist[t] + g[t][j]);
}
if(dist[n] == 0x3f3f3f3f) return -1;
return dist[n];
}
int main()
{
scanf("%d%d", &n, &m);
memset(g, 0x3f, sizeof(g));
while (m--)
{
int x, y, c;
scanf("%d%d%d", &x, &y, &c);
g[x][y] = min(g[x][y], c);
}
cout << dijkstra() << endl;
return 0;
}
堆优化版dijkstra适合稀疏图
思路
堆优化版的dijkstra是对朴素版dijkstra进行了优化，在朴素版dijkstra中时间复杂度最高的寻找距离
最短的点O(n^2)可以使用最小堆优化。
1. 一号点的距离初始化为零，其他点初始化成无穷大。
2. 将一号点放入堆中。
3. 不断循环，直到堆空。每一次循环中执行的操作为：
弹出堆顶（与朴素版diijkstra找到S外距离最短的点相同，并标记该点的最短路径已经确定）。
用该点更新临界点的距离，若更新成功就加入到堆中。
时间复杂度分析
寻找路径最短的点：$O(n)$
加入集合S：$O(n)$
更新距离：$O(mlogn)$
具体问题
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
typedef pair<int, int> PII;
const int N = 100010; // 把N改为150010就能ac
// 稀疏图用邻接表来存
int h[N], e[N], ne[N], idx;
int w[N]; // 用来存权重
int dist[N];
bool st[N]; // 如果为true说明这个点的最短路径已经确定
int n, m;
void add(int x, int y, int c)
{
// 有重边也不要紧，假设1->2有权重为2和3的边，再遍历到点1的时候2号点的距离会更新两次放入堆中
// 这样堆中会有很多冗余的点，但是在弹出的时候还是会弹出最小值2+x（x为之前确定的最短路径），
// 并标记st为true，所以下一次弹出3+x会continue不会向下执行。
w[idx] = c;
e[idx] = y;
ne[idx] = h[x];
h[x] = idx++;
}
int dijkstra()
{
memset(dist, 0x3f, sizeof(dist));
dist[1] = 0;
priority_queue<PII, vector<PII>, greater<PII>> heap; // 定义一个小根堆
// 这里heap中为什么要存pair呢，首先小根堆是根据距离来排的，所以有一个变量要是距离，
// 其次在从堆中拿出来的时候要知道知道这个点是哪个点，不然怎么更新邻接点呢？所以第二个变量要存点。
heap.push({ 0, 1 }); // 这个顺序不能倒，pair排序时是先根据first，再根据second，
// 这里显然要根据距离排序
while(heap.size())
{
PII k = heap.top(); // 取不在集合S中距离最短的点
heap.pop();
int ver = k.second, distance = k.first;
if(st[ver]) continue;
st[ver] = true;
for(int i = h[ver]; i != -1; i = ne[i])
{
int j = e[i]; // i只是个下标，e中在存的是i这个下标对应的点。
if(dist[j] > distance + w[i])
{
dist[j] = distance + w[i];
heap.push({ dist[j], j });
}
}
}
if(dist[n] == 0x3f3f3f3f) return -1;
else return dist[n];
}
int main()
{
memset(h, -1, sizeof(h));
scanf("%d%d", &n, &m);
while (m--)
{
int x, y, c;
scanf("%d%d%d", &x, &y, &c);
add(x, y, c);
}
cout << dijkstra() << endl;
return 0;
}
连线很多的时候，对应的就是稠密图，显然易见，稠密图的路径太多了，所以就用点来找，也就是抓重点；
点很多，但是连线不是很多的时候，对应的就是稀疏图，稀疏图的路径不多，所以按照连接路径找最短路，这个过程运用优先队列，能确保每一次查找保留到更新到队列里的都是最小的，同时还解决了两个点多条路选择最短路的问题；
%%！ 大佬解开了我的疑惑，orzorz！！！！
%😏
int h[N], e[M], ne[M], w[M], idx;
链式前向星的正确写法，养成好习惯！！
大家看好M,不信可以去试下1129.热浪
希望以后的人不要再犯这种错误，我改了半小时才发现这个错误。。
嗯嗯，不过这道题n,m的范围一样
我找第一道有这个的，提醒下后面的人
N表示节点个数，h[N]，表示每个头结点，其他的都和边数有关系，所以是M
谢谢大佬！！！
看了您的代码之后，我终于知道冗余的点是如何出现以及如何处理的啦，也终于意识到为什么要用小根堆了，，，
那我说一下自己的理解：每一次进行dist中数据优化时，每进行一次，就会有一个j计入优先队列，但是由于小根堆的性质，只有最小的才会被第一个弹出，因而之后的就理所当然地被continue了。
可能还是有一些疏漏，因为优先队列里元素的变化情况还是一知半解，在这里蹲一个大佬解答，，，
（有图更好）
我还是不明白continue的意义
因为代码中的for循环会把所有满足dist[j] > distance + w[i]的点都加进去，有的点它既是a的邻接点又是b的邻接点，这样的点可能会在将a的邻接点更新的时候加进去一次，又在更新b的邻接点的时候又加进去一次，这样队列中就有两个一样的点，虽然距离不同
厉害！救了我一命，我一直想不出为啥堆优化还要st数组，因为距离被更新的点才会进堆，我认为一个点不会反复进堆啊因为一旦距离确定就不可能再更新距离，谁知道一个点竟然是同时以不同距离的状态多次进堆了哈哈
如果将两个中较小的那个取出，剩下的那个距离更大的点就是没用的点，如果不用continue跳过他将会影响后面其他点的取值，这样理解对吗
不用continue不会影响后面的取值，因为有dis[j]>distance+w[i]的判断，一定会更新成最小的那个，只不过就是把这个点的邻接点又加进去判断了而已，多了几次for循环，加上continue会减少这个判断，不加continue会超时，不会答案错误。
为什么要continue呢，是因为st数组就是判断这个点的最短路是否已经被确定了，如果是true说明这个点已经确定了，没必要再进行下去了，这个容易和spfa弄混，spfa是不断更新边，因为spfa可以处理负权值的图，dijkstra是不行的，是基于贪心的，因为堆优化的dijkstra会把距离原点最近的点point利用小根堆的特性找出来，以这个点point作为更新点，来更新point的邻接点，如果st[point]=true，说明这个点已经确定了最短的距离，而且他的邻接点在后面的for循环中也被更新过了，自己也变成了true，如果再找到的话，没必要再更新了，无非就是多了判断，也进不了堆里面。
感谢大佬
感谢巨佬
大佬，想问下if（dist[t] > distance + w[i])这里，为什么用!st[j]会超时呀？
会存在一个点已经计算过最短路了，由于前面更新的时候，导致这个点可能被加进来多次，队列里面还存在这个点，这时候st[ver]==true就continue就可以了
感谢大佬！！
感谢大佬！！
一直在想用队列可不可以，在大佬这层搞明白了，不可以的。如果用队列的话，当出现一个点二次进队的情况时（既然能二次进队，就证明第二次更新的距离更短），如果此时不用st数组来表明状态的话，那么就有重复性工作（即同一个点距离长的跟更新了一遍，距离短的又跟新了一遍）此时可能思路正确，但是会超时，如果用st数组来表明状态的话，那么第二次进队的那个距离短的情况就不能去更更新了。
厉害,我也在想为什么还要st数组有什么用
感谢(❁´ω`❁)彻底理解了
也有解决重边的作用吧
那个“pair排序时是先根据first，再根据second“的注释让我醍醐灌顶，我写的时候是反着写的，将节点编号作为first，再将距离作为second，然后代码一直错误，找不到原因，看到这篇题解让我知道我的错误在哪了，谢谢大佬%%%
我没注意看注释。对着代码查了好久。。看到你的评论终于解放了。。。
大家要理解算法的本质，在探讨continue的作用不要把朴素版和堆优化版分开来看。因为dijkstra算法本质上是两个集合，第一个集合存放已经确定最短距离的点，另一个集合存放没有确定最短距离的点，最开始第一个集合只有源点，因为源点到自己的距离是0，后面我们需要不断从第一个集合里面找出距离源点最近且没有使用过的点，利用这个点来更新距离，同时对这个点的状态进行标记，因此确定过的点不能再作为中间点，因为他已经使用过了。（为什么不能再确定，这里就不说了，因为我们利用了贪心的思想）。所以一开始队列加入了源点，源点此时没有使用过，我们需要用它来更新距离，然后我们利用源点更新过的点就可以加入到队列中，利用小根堆的特性找出没有使用过的距离源点最近的点，但是这里有个问题，就是源点一定会被再次选出来，因为距离是0，所以要continue，再次找出一个没被使用过的点，继续下去。
这是我的看法，欢迎大家评论，帮助我完善，我目前认为我的想法是正确的。
理解有问题
结合评论区大佬们的解释加上自己的理解，有的小伙伴可能会疑惑 continue的作用，以为一个点不会反复进堆，因为一旦距离确定就不可能再更新距离。实际上，我们来看代码，for循环会把所有满足dist[j] > distance + w[i] 的点都加入堆，有的点比如 c 它既是 a 的邻接点又是 b的邻接点，这样的点可能会在将 a 的邻接点更新的时候加进去一次，又在更新 b 的邻接点的时候又加进去一次，这样队列中就有两个编号一样、距离不同的点。因此一个点可能同时以不同距离的状态多次进堆。但实际上 dist[c]在被第一个点更新完后就确定了，因为我们 Dijkstra 是每次取出一个全局最小的dist来更新别的点，每个点的最短距离一定是递增的，不可能出现后面进入集合 S 的点还会更新出 更短的 邻接点的最短路径，所以我们第一次就直接可以把 st 置为true，后面再碰到直接跳过啦！
不需要想那么多，理解算法本质就行了。因为dijkstra算法本质上是两个集合，第一个集合存放已经确定最短距离的点，另一个集合存放没有确定最短距离的点，最开始第一个集合只有源点，因为源点到自己的距离是0，后面我们需要不断从第一个集合里面找出距离源点最近且没有使用过的点，利用这个点来更新距离，同时对这个点的状态进行标记，因此确定过的点不能再作为中间点，因为他已经使用过了。
所以一开始队列加入了源点，源点此时没有使用过，我们需要用它来更新距离，然后我们利用源点更新过的点就可以加入到队列中，利用小根堆的特性找出没有使用过的距离源点最近的点，但是这里有个问题，就是源点一定会被再次选出来，因为距离是0，所以要continue，再次找出一个没被使用过的点，继续下去。
不是吧，源点在第一次就被踢除了，哪怕之后有点指向源点，距离也不会小于0
大佬，最后一个代码
priority_queue<PII, vector<PII>, greater<PII>> heap; // 定义一个小根堆这里
greater<PII>后面要加上一个空格，不然会报错有些IDE里面会把这种>>识别成重载
不会的，在C++11中把这个bug去了。
好的，谢谢
感觉 if(st[ver]) continue这个剪枝 还可以再优化成 if(dist[ver]<dis) continue 这样还能剪掉：当前点虽未确定最小距离，但当前点信息中的距离大于此点已知最小距离的情况 这种情况再用当前点信息来更新相邻点离源点的距离没有意义
这个布尔数组st可以不要
终于看到时间复杂度写对的题解了，优化版查找最小值显然是O（n）而非O（1）
求助，邻接表的详解有没有推荐的博客看看？一直没搞懂（会链式前向星）
这个不就是链式前向星嘛（懵
看懂了，大佬tql
更新距离的时间复杂度为什么是O(m)啊， 不应该是O(n ^ 2)吗
每个点应该只会被它的入点更新一次吧，所以加起来就是 $m$ 次更新，复杂度次更新，复杂度 $O(mlog_2n)$
为啥是mlogn啊，不是m吗？难道是小根堆本身存的时候会产生logn的复杂度？
插入堆调整的复杂度是$O(log_2n)$（或$O(log_2m)$）
好的，谢谢哈
朴素版是对所有点进行遍历，稠密图中的边较多，所以使用朴素版较好，稀疏图点较多，堆优化版是通过边来查找最短路，所以稀疏图使用堆优化版
xdm，想请教一下大家，Dijkstra Ⅱ堆优化版算法那一题，为什么用 SPFA 算法显示超时呀？
难道 Dijkstra Ⅱ那一题就是极特殊的只能用 Dijkstra 算法，不能用 SPFA 算法的图么？
这题为啥不能开long long?
这个权重是什么意?
可以把权值加一个负号，然后可以用大根堆来写了
为什么输出和标准答案不一样呢
这个也可以用map的吧