850 Dijkstra求最短路 II（堆优化版本的Dijkstra算法）

迈不过友情╰ 2022-09-15 13:56 168阅读 0赞

**1. 问题描述：**

给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环，所有边权均为非负值。请你求出 1 号点到 n 号点的最短距离，如果无法从 1 号点走到 n 号点，则输出 −1。

**输入格式**

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

**输出格式**

输出一个整数，表示 1 号点到 n 号点的最短距离。如果路径不存在，则输出 −1。

**数据范围**

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

**输入样例：**

3 3  
1 2 2  
2 3 1  
1 3 4

**输出样例：**

3  
来源：[https://www.acwing.com/problem/content/description/852/][https_www.acwing.com_problem_content_description_852]

**2. 思路分析：**

这道题目与[849题Dijkstra求最短路 I][849_Dijkstra_ I]的题目是一模一样的的，只是数据范围扩大了，如果我们使用朴素版本的Dijkstra算法求解，时间复杂度为O（n ^ 2）肯定会超时，所以我们必须对之前的算法进行优化才能够通过；朴素版本的Dijkstra算法的瓶颈在于寻找当前还没有被访问且与起点s距离最近的点，每一次找这个点的时候都需要循环n次，基于这个想法我们想到从这个瓶颈对之前的算法进行优化，我们可以借助于小根堆来存储与起点s距离最近的点；因为使用的是python语言所以使用heapq模块来模拟小根堆，我们可以声明一个列表q，每一次heapq模块是对列表q进行操作（heapqush和heapop操作），在往列表q中加入元素之后将列表调整为一个小根堆，弹出元素之后将列表q调整为小根堆；具体的操作：一开始时候往q中加入起点信息，包含两个信息，python可以使用元组来封装这些信息，c++可以使用pair，第一个信息是从起点到这个点的最短距离，第二个信息是这个点的编号，当q不为空的时候执行循环，一开始的时候弹出堆顶元素，然后判断弹出元素的点到下一个点的距离是否更短，如果更短那么将到这个点的最短距离与下一个点的编号作为元组加入到q中，...一直到q为空就结束了；假设有向图中点的个数为n，边的个数为m，所以最多有n(n - 1) / 2条边，也即m最多可以看成是n ^ 2，而最多可以更新m次，堆中的边最多为m，调整为小根堆的时间复杂度为O(logm） = O(logn ^ 2) = O(2logn) = O(logn)，所以时间复杂度为O(mlogn)，则总的时间复杂度为O(1.5 \* 10 ^ 5 \* 20) = O（3 \* 10 ^ 6）是可以通过的。

**3. 代码如下：**

from typing import List
    import heapq
    
    
    class Solution:
        # 这里找距离起点最近的点的基础上使用堆来维护最小的那个距离以及对应的下标(优化)
        # s为起点, t为终点, n为图中节点的数目, g为有向图
        def dijkstra(self, s: int, t: int, n: int, g: List[dict]):
            vis = [0] * (n + 1)
            INF = 10 ** 10
            dist = [INF] * (n + 1)
            dist[s] = 0
            q = list()
            heapq.heappush(q, (0, s))
            while q:
                # 注意这里使用的是heapq.pop而不是pop之前答案是错的老是检查不出错误, 贼坑
                cur = heapq.heappop(q)
                # 有的点可能加入两次所以需要判断一下是否被访问过了, 例如题目中的测试数据就是这样的, 3这个点被加入了两次但是一旦这个点被标记了一次说明这个点到其余点的最短距离已经更新完了再更新就没有意思了属于一个小优化, 不加会超时
                if vis[cur[1]] == 1: continue
                vis[cur[1]] = 1
                # next为当前节点的下一个点的信息,next为一个元祖, next[0]是下一个点的编号, next[1]是权重
                for next in g[cur[1]].items():
                    # cur[0]是从起点到cur[1]的最短距离
                    if dist[next[0]] > cur[0] + next[1]:
                        dist[next[0]] = cur[0] + next[1]
                        heapq.heappush(q, (dist[next[0]], next[0]))
            # print(dist)
            return dist[t] if dist[t] != INF else -1
    
        # 使用小根堆来优化
        def process(self):
            n, m = map(int, input().split())
            # 每一个g[i]都是一个字典这样可以很方便地找对应节点的权重
            g = [dict() for i in range(n + 1)]
            for i in range(m):
                x, y, z = map(int, input().split())
                # if判断可以处理重边的情况, 取的是权重最小的那条边
                if y in g[x]:
                    g[x][y] = min(g[x][y], z)
                else:
                    g[x][y] = z
            return self.dijkstra(1, n, n, g)
    
    
    if __name__ == "__main__":
        print(Solution().process())

[https_www.acwing.com_problem_content_description_852]: https://www.acwing.com/problem/content/description/852/
[849_Dijkstra_ I]: https://blog.csdn.net/qq_39445165/article/details/120728336