dijkstra + 堆优化
dijkstra + 堆优化什么是dijkstra？
dijkstra是一种单源最短路算法，朴素版的dijkstra可以在O(n^2)的时间复杂度求出最短路径长度；与之相应的还有堆优化版的dijkstra，经过优化后的时间复杂度可以达到O((n+m)log_2n)，再进阶的话还有线段树优化与斐波那契堆优化。和dijkstra相似的算法还有spfa，但是目前竞赛上随手卡一下spfa已经成了众多出题人的习惯。
什么时候用dijkstra？
由于dijkstra的核心思想是贪心
所以是不可以应用于有负权边的图
朴素dijkstra的流程
[*]读入m条边，使用二维数组g记录i到j的距离为g;
[*]定义数组dist[]，代表储存起始点到i的距离为dist;
❝ memset(dist, 0x3f, sizeof(dist));
❞
[*]定义数组st[]，st=1;代表第i个点已经确定其到起点的最短距离
[*]由于起点到起点的距离为0，所以使dist=0;
[*]n个点迭代n次，即确定每个点到起点的最小值
❝ for (int i = 1; i <= n; i ++)
❞
[*]每次迭代的过程中找到未确定最短距离的点中最短的点
int t = -1;
for (int j = 1; j <= n; j ++)
if (!st && (dist < dist || t == -1))
t = j;
[*]然后利用找到的这个点去更新其他未确定但与它相通的点的距离
for (int j = 1; j <= n; j ++)
dist = min(dist, dist + g);
图解
首先我们设起点是1号节点
image-20221103000439246
此时dist=0,st=1，我们以蓝色节点为标记作为我们已经更新过的点
接下来是n次迭代，在第一次迭代中，我们通过1号节点去更新其他节点，如果1号节点到与他相通的节点的距离小于dist，那么我们便更新它的距离
dist = dist = INF 括号里面的值代表变量值
dist > dist (0) + g (3)
dist > dist (0) + g (5)
dist = dist + g = 3
dist = dist + g = 5
到了第二次迭代，通过以下代码，我们找到了dist最小，且为被标记的节点2
int t = -1;
for (int j = 1; j <= n; j ++)
if (!st && (dist < dist || t == -1))
t = j;
那么我们将节点2标记一下，代表此时的dist已经是到起点的最短距离了st = 1;
image-20221103000514934
接下来再根据节点2相邻的点去更新其他节点的距离
dist = dist = INF
dist = min(dist, dist (3) + g (10)) = 13
dist = min(dist, dist (3) + g (20)) = 23
(以下的代码省略已经标记的点)
dist = min(dist (0), dist (3) + g (3)) = 0
接下来进入第三次迭代，我们找到了距离起点最近的节点3（即dist最小的点）
那么在把节点3标记一下，再利用节点3去更新与他相通 的点的距离
dist = 13(上一次迭代中更新得到的)
dist = min(dist (13), dist (5) + g (4)) = 9
虽然上一次迭代已经将节点4到起点的距离从inf更新成了13，但是我们后来发现如果从节点3开始走的话，到节点4的距离更短，那么此时我们就把节点4在更新一下，得到dist = 9;
image-20221103000521189
到了第四次迭代，发现dist最小的节点（即到起点距离最短的节点）是4，那么再标志一下4去更新与他相通的点
dist = 23
dist = min(dist, dist (9) + g (7)) = 16
显然dist会更新为16
image-20221103000527165
到了第五次迭代，我们发现已经没有可以更新的点了，最后剩下的节点我们直接标记一下就可以结束了。
image-20221103000537436
而我们也得到了所以点到起点的最短距离（即最短路径）
dist = 0, dist = 3, dist = 5, dist = 9, dist = 16
dijkstra为什么可以通过上述的操作来保证得到的dist是最短距离？
由于图是没有负权边的，所以最小值也是不会在被更新的。我们不断选择全局最小值进行标记和更新，即贪心的用最小值去找最小值，最终是可以保证每个节点最后的距离都是最短路径的距离。
全代码
int dijkstra() {
memset(dist, 0x3f, sizeof(dist));
dist = 0;
for (int i = 1; i <= n; i ++) {
int t = -1;
for (int j = 1; j <= n; j ++)
if (!st && (dist < dist || t == -1))
t = j;
for (int j = 1; j <= n; j ++)
dist = min(dist, dist + g);
st = 1;
}
}
堆优化
在上述流程中，我们发现要想找到数组dist最小的节点，是需要O(n)的时间复杂度去遍历所有的点，而这一个操作也是朴素版dijkstra时间复杂度为O(n^2)的主要原因。
那么我们该如何优化它呢？很简单，我们可以维护一个堆，用堆来储存我们下一个需要用来更新的节点，取出堆顶元素的时间复杂度为O(log_2n)，是远快于便利所有节点的，再用O(log_2n)遍历每一条边，时间复杂度为O((n+m)log_2n)
由于堆优化与边的数量有关，所以一般运用于稀疏图。
不会堆怎么办？手写堆的话又太麻烦了
我们可以用优先队列啊！priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
而优先队列我们使用pair类型，这是由于我们将会用优先队列储存两个信息：
[*]distance，即到起点的距离
[*]ver，即第几号节点
而储存时我们也要注意要将距离放在第一个位置（first)，因为pair默认的排序是以第一个数来作为基值去排序的。q.push({distance, ver});
而提取dist最小的节点的信息也十分简单
auto t = q.top();
q.pop();
int ver = t.second, distance = t.first;
当然，要注意一下这个节点有没有被标记过（即已经更新过其相邻节点的距离），如果被标记过那么就不需要继续下去了。
if(st) continue;
由于我们稀疏图常用邻接链表储存，所以遍历该节点相邻其他节点方式也有些差异
for(int i = head; i; i = meg.ne){
int j = meg.to;
if(dist > meg.w + distance){
dist = meg.w + distance;
q.push({dist, j});//如果这个点被更新过了，那么就加入到优先队列中，以便用它更新于它相通的节点
}
}
全代码
int dijkstra(){
memset(dist, 0x3f, sizeof(dist));
dist = 0;
q.push({0, 1});
while(q.size()){
auto t = q.top();
q.pop();
int ver = t.second, distance = t.first;
if(st) continue;
st = 1;
for(int i = head; i; i = meg.ne){
int j = meg.to;
if(dist > meg.w + distance){
dist = meg.w + distance;
q.push({dist, j});
}
}
}
return dist;
} 优先队列默认是最大堆吧，不能写成默认的形式 抱歉是我疏忽了，已经改正啦，谢谢提醒ww[爱]
页:
[1]