dijkstra + 堆优化

x498015000

dijkstra + 堆优化

什么是dijkstra？

dijkstra是一种单源最短路算法，朴素版的dijkstra可以在O(n^2)的时间复杂度求出最短路径长度；与之相应的还有堆优化版的dijkstra，经过优化后的时间复杂度可以达到O((n+m)log_2n)，再进阶的话还有线段树优化与斐波那契堆优化。和dijkstra相似的算法还有spfa，但是目前竞赛上随手卡一下spfa已经成了众多出题人的习惯。
什么时候用dijkstra？

由于dijkstra的核心思想是贪心
所以是不可以应用于有负权边的图
朴素dijkstra的流程

• 读入m条边，使用二维数组g[j]记录i到j的距离为g[j];
  
• 定义数组dist[]，代表储存起始点到i的距离为dist;
  ❝ memset(dist, 0x3f, sizeof(dist));
  ❞
  
• 定义数组st[]，st=1;代表第i个点已经确定其到起点的最短距离
  
• 由于起点到起点的距离为0，所以使dist[start]=0;
  
• n个点迭代n次，即确定每个点到起点的最小值
  ❝ for (int i = 1; i <= n; i ++)
  ❞
  
• 每次迭代的过程中找到未确定最短距离的点中最短的点
  int t = -1;
  for (int j = 1; j <= n; j ++)
  if (!st[j] && (dist[j] < dist[t] || t == -1))
             t = j;
  
• 然后利用找到的这个点去更新其他未确定但与它相通的点的距离
  for (int j = 1; j <= n; j ++)
       dist[j] = min(dist[j], dist[t] + g[t][j]);
  

图解

首先我们设起点是1号节点



image-20221103000439246

此时dist[1]=0,st[1]=1，我们以蓝色节点为标记作为我们已经更新过的点



接下来是n次迭代，在第一次迭代中，我们通过1号节点去更新其他节点，如果1号节点到与他相通的节点的距离小于dist，那么我们便更新它的距离
dist[2] = dist[3] = INF    括号里面的值代表变量值
dist[2] > dist[1] (0) + g[1][2] (3)
dist[3] > dist[1] (0) + g[1][3] (5)
dist[2] = dist[1] + g[1][2] = 3
dist[3] = dist[1] + g[1][3] = 5
到了第二次迭代，通过以下代码，我们找到了dist最小，且为被标记的节点2
int t = -1;
for (int j = 1; j <= n; j ++)
     if (!st[j] && (dist[j] < dist[t] || t == -1))
           t = j;
那么我们将节点2标记一下，代表此时的dist[2]已经是到起点的最短距离了st[t] = 1;



image-20221103000514934

接下来再根据节点2相邻的点去更新其他节点的距离
dist[4] = dist[5] = INF
dist[4] = min(dist[4], dist[2] (3) + g[2][4] (10)) = 13
dist[5] = min(dist[5], dist[2] (3) + g[2][5] (20)) = 23
(以下的代码省略已经标记的点)
dist[1] = min(dist[1] (0), dist[2] (3) + g[2][1] (3)) = 0
接下来进入第三次迭代，我们找到了距离起点最近的节点3（即dist最小的点）
那么在把节点3标记一下，再利用节点3去更新与他相通 的点的距离
dist[4] = 13(上一次迭代中更新得到的)
dist[4] = min(dist[4] (13), dist[3] (5) + g[3][4] (4)) = 9
虽然上一次迭代已经将节点4到起点的距离从inf更新成了13，但是我们后来发现如果从节点3开始走的话，到节点4的距离更短，那么此时我们就把节点4在更新一下，得到dist[4] = 9;



image-20221103000521189

到了第四次迭代，发现dist最小的节点（即到起点距离最短的节点）是4，那么再标志一下4去更新与他相通的点
dist[5] = 23
dist[5] = min(dist[5], dist[4] (9) + g[4][5] (7)) = 16
显然dist[5]会更新为16



image-20221103000527165

到了第五次迭代，我们发现已经没有可以更新的点了，最后剩下的节点我们直接标记一下就可以结束了。



image-20221103000537436

而我们也得到了所以点到起点的最短距离（即最短路径）
dist[1] = 0, dist[2] = 3, dist[3] = 5, dist[4] = 9, dist[5] = 16
dijkstra为什么可以通过上述的操作来保证得到的dist是最短距离？

由于图是没有负权边的，所以最小值也是不会在被更新的。我们不断选择全局最小值进行标记和更新，即贪心的用最小值去找最小值，最终是可以保证每个节点最后的距离都是最短路径的距离。
全代码

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 (!st[j] && (dist[j] < dist[t] || t == -1))
                t = j;
        for (int j = 1; j <= n; j ++)
            dist[j] = min(dist[j], dist[t] + g[t][j]);
        st[t] = 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[ver]) continue;
由于我们稀疏图常用邻接链表储存，所以遍历该节点相邻其他节点方式也有些差异
for(int i = head[ver]; i; i = meg.ne){
    int j = meg.to;
    if(dist[j] > meg.w + distance){
          dist[j] = meg.w + distance;
          q.push({dist[j], j});//如果这个点被更新过了，那么就加入到优先队列中，以便用它更新于它相通的节点
     }
}   
全代码

int dijkstra(){
    memset(dist, 0x3f, sizeof(dist));
    dist[1] = 0;
    q.push({0, 1});
    while(q.size()){
        auto t = q.top();
        q.pop();
        int ver = t.second, distance = t.first;
        if(st[ver]) continue;
        st[ver] = 1;
        for(int i = head[ver]; i; i = meg.ne){
            int j = meg.to;
            if(dist[j] > meg.w + distance){
                dist[j] = meg.w + distance;
                q.push({dist[j], j});
            }
        }   
    }
    return dist[n];
}

ainatipen

优先队列默认是最大堆吧，不能写成默认的形式

kyuskoj

抱歉是我疏忽了，已经改正啦，谢谢提醒ww[爱]