堆优化版Dijkstra算法

系统管理员 2022-11-06 08:53 150阅读 0赞

**上一篇博客：[朴素Dijkstra算法][Dijkstra]**

>  写在前面：大家好！我是`AC-fun`,我的昵称来自两个单词`Accepted`和`fun`。我是一个热爱ACM的蒟蒻。如果博客中有不足或者的错误的地方欢迎在评论区或者私信我指正，感谢大家的不吝赐教。我的唯一博客更新地址是：[https://ac-fun.blog.csdn.net/][https_ac-fun.blog.csdn.net]。非常感谢大家的支持。一起加油，冲鸭！  
>  `用知识改变命运，用知识成就未来！加油 (ง •̀o•́)ง (ง •̀o•́)ง`

### 文章目录 ###

*  简介
 *  优化思路
 *  时间复杂度
 *  算法实现
 *  例题
 *   *  题目信息
     *   *  题目描述
         *  输入格式
         *  输出格式
         *  数据范围
         *  输入样例
         *  输出样例
     *  题解
     *   *  解题代码

# 简介 #

上一篇博客提到的 [朴素Dijkstra算法][Dijkstra] 适用于求 **稠密图** 的最短路问题，因为 **稠密图** 的边数远远大于点数，朴素Dijkstra算法的思路为进行 **n** 次循环，每次循环再遍历 **n** 个点确定一个还未确定最短距离的点中距离源点最近距离的点，然后再用这个点更新其所能到达的点（算法默认当前的点可以到达所有的点，因为没有到达的点之间的距离都已经初始化为正无穷大，所以不会被更新，不影响结果）。时间复杂度为 **O(n2)**。

对于 **稀疏图** 来说，由于边数与点数相差不大，一个点所能到达的点比较少，所以用 **邻接表** 来存储效率比较高。在确定一个还未确定最短距离的点中距离源点最近距离的点时 **朴素Dijkstra** 的方法是遍历所有的点通过比较找出最近的点，在这个地方可以使用 **优先队列** 来进行优化，通过 **优先队列** 优化后 **朴素Dijkstra算法** 就叫做 `堆优化版的Dijkstra算法`。

# 优化思路 #

首先将 **优先队列** 定义成 **小根堆**，将源点的距离初始化为 **0** 加入到优先队列中，然后从这个点开始扩展。先将队列中的队头元素 **ver** 保存到一个临时变量中，并将队头元素出队，然后遍历这个点的所有出边所到达的点 **j**，更新所有到达的点距离源点最近的距离。

如果源点直接到 **j** 点的距离比源点先到 **ver** 点再从 **ver** 点到 **j** 点的距离大，那么就更新 **dist\[j\]**，使 **dist\[j\]** 到源点的距离最短，并将该点到源点的距离以及该点的编号作为一个 **pair** 加入到优先队列中，然后将其标记，表示该点已经确定最短距离。因为是小根堆，所以会根据距离进行排序，距离最短的点总是位于队头。一直扩展下去，直到队列为空。

因为有 **重边** 的缘故，所以该点可能会有冗余数据，即如果在扩展的时候，第一次遍历到的点是 **2** 号点，距离 **源点** 的距离为 **10**，此时 **dist\[2\] = 0x3f3f3f3f > dist\[1\] + distance\[1 -> 2\] = 0 + 10 = 10** 所以 **dist\[2\]** 会被更新为 **10**，此时会将 **\{10, 2\}** 入队。但是很不巧从 **源点** 到 **2** 号点有一个距离为 **6** 的重边，当遍历到这个重边时，由于 **dist\[2\] = 10 > dist\[1\] + distance\[1 -> 2\] = 0 + 6 = 6**,所以 **\{6, 2\}** 也入队了，入队之后由于是 **小根堆** 所以 **\{6, 2\}** 会排在 **\{10, 2\}** 前面，所以 **\{6, 2\}** 会先出队，出队之后会被标记。所以当下一次再遇到已经被标记的 **2** 号点时，直接 `continue` 忽略掉冗余数据继续扩展下一个点即可。

# 时间复杂度 #

总共需要遍历 **m** 条边，插入数据修改小根堆的时间复杂度为 **O( l o g   n log\\ n log n)**，所以时间复杂度为 **O( m ∗ l o g   n m\*log\\ n m∗log n)**。因为对于 **稀疏图** 来说边数与点数很接近，所以可以看做为 **O( n ∗ l o g   n n\*log\\ n n∗log n)**。但是对于 **稠密图** 来说边数接近点数的平方个，如果稠密图使用堆优化版的Dijkstra算法，那么时间复杂度将会是 **O( n 2 ∗ l o g   n n^2\*log\\ n n2∗log n)**，显然不如直接使用朴素Dijkstra算法。所以 `堆优化版的Dijkstra算法` 更适用于 **稀疏图** ，而 `朴素Dijkstra算法` 更适用于 **稠密图**。

# 算法实现 #

int dijkstra() { 
        memset(dist, 0x3f, sizeof dist);
        dist[1] = 0;
        // 定义小根堆
        priority_queue<PII, vector<PII>, greater<PII>> heap;
        heap.push({ 0, 1}); // 先将最短的距离添加到小根堆中
        
        while (heap.size()) { 
            auto t = heap.top(); // 取出当前已经确定的最短距离的点
            heap.pop();
            
            int ver = t.second;
            if (st[ver]) continue; // 如果已经被标记过，说明当前的点的边是比较长的重边，直接跳过。
            st[ver] = true;
            
            // 使用当前距离最短的点来更新其出边
            for (int i = h[ver]; i != -1; i = ne[i]) { 
                int j = e[i]; // j 为 ver 出边所到达的点
                if (dist[j] > dist[ver] + w[i]) { 
                    /* 如果源点直接到 j 点的距离比源点先到 ver 点再从 ver 点到 j 点的距离大， 那么就更新 dist[j]，使dist[j] 到源点的距离最短 */
                    dist[j] = dist[ver] + w[i];
                    // 将下一个距离源点最近的点添加到小根堆中
                    heap.push({ dist[j], j});
                }
            }
        }
        
        if (dist[n] == 0x3f3f3f3f) return -1;
        return dist[n];
    }

# 例题 #

题目来源：[AcWing 850. Dijkstra求最短路 II][AcWing 850. Dijkstra_ II]

## 题目信息 ##

### 题目描述 ###

给定一个 **n** 个点 **m** 条边的有向图，图中可能存在重边和自环，所有边权均为非负值。

请你求出 **1** 号点到 **n** 号点的最短距离，如果无法从 **1** 号点走到 **n** 号点，则输出 `-1`。

### 输入格式 ###

第一行包含整数 **n** 和 **m**。

接下来 **m** 行每行包含三个整数 **x，y，z** 表示存在一条从点 **x** 到点 **y** 的有向边，边长为 **z**。

### 输出格式 ###

输出一个整数，表示 **1** 号点到 **n** 号点的最短距离。

如果路径不存在，则输出 `-1`。

### 数据范围 ###

**1 ≤ n,m ≤  1.5 × 1 0 5 1.5×10^5 1.5×105,**  
 图中涉及边长均不小于 **0**，且不超过 **10000**。

### 输入样例 ###

> **3 3  
> 1 2 2  
> 2 3 1  
> 1 3 4**

### 输出样例 ###

> **3**

## 题解 ##

### 解题代码 ###

#include <iostream>
    #include <cstring>
    #include <cstdio>
    #include <algorithm>
    #include <queue>
    
    using namespace std;
    
    typedef pair<int, int> PII; // 第一个存距离，第二个存点的编号
    
    const int N = 1000010;
    int n, m;
    int h[N], w[N], e[N], ne[N], idx; // 使用邻接表存储稀疏图
    int dist[N];
    bool st[N];
    
    void add(int a, int b, int c) { 
        e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
    }
    
    int dijkstra() { 
        memset(dist, 0x3f, sizeof dist);
        dist[1] = 0;
        // 定义小根堆
        priority_queue<PII, vector<PII>, greater<PII>> heap;
        heap.push({ 0, 1}); // 先将最短的距离添加到小根堆中
        
        while (heap.size()) { 
            auto t = heap.top(); // 取出当前已经确定的最短距离的点
            heap.pop();
            
            int ver = t.second;
            if (st[ver]) continue; // 如果已经被标记过，说明当前的点的边是比较长的重边，直接跳过。
            st[ver] = true;
            
            // 使用当前距离最短的点来更新其出边
            for (int i = h[ver]; i != -1; i = ne[i]) { 
                int j = e[i]; // j 为 ver 出边所到达的点
                if (dist[j] > dist[ver] + w[i]) { 
                    /* 如果源点直接到 j 点的距离比源点先到 ver 点再从 ver 点到 j 点的距离大， 那么就更新 dist[j]，使dist[j] 到源点的距离最短 */
                    dist[j] = dist[ver] + w[i];
                    // 将下一个距离源点最近的点添加到小根堆中
                    heap.push({ dist[j], j});
                }
            }
        }
        
        if (dist[n] == 0x3f3f3f3f) return -1;
        return dist[n];
    }
    
    int main() { 
        scanf("%d%d", &n, &m);
        
        memset(h, -1, sizeof h); // 将每一条边的头结点初始化为 -1
        // 输入 m 条边
        while (m--) { 
            int a, b, c;
            scanf("%d%d%d", &a, &b, &c);
            add(a, b, c);
        }
        cout << dijkstra() << endl;
        return 0;
    }

--------------------

> 未完待续，持续更新中……  
> ![2021030823581715.png][]

[Dijkstra]: https://ac-fun.blog.csdn.net/article/details/114372108
[https_ac-fun.blog.csdn.net]: https://ac-fun.blog.csdn.net/
[AcWing 850. Dijkstra_ II]: https://www.acwing.com/problem/content/description/852/
[2021030823581715.png]: /images/20221023/35ad29ac92614520a92a46159b740040.png