849 Dijkstra求最短路 I（朴素Dijkstra算法模板）

「爱情、让人受尽委屈。」 2022-09-15 12:56 193阅读 0赞

**1. 问题描述：**

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

**输入格式**

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

**输出格式**

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

**数据范围**

1 ≤ n ≤ 500，  
1 ≤ m ≤ 10 ^ 5，  
图中涉及边长均不超过10000。

**输入样例：**

3 3  
1 2 2  
2 3 1  
1 3 4

**输出样例：**

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

**2. 思路分析：**

这道题目属于最短路径的裸题，因为边的权重都是正数，所以可以使用Dijkstra算法解决，Dijkstra算法用来求解从起点s到终点t的最短路径，因为n = 500，所以使用**朴素版的Dijkstra算法**也是可以通过的，时间复杂度为O(n ^ 2) = 2.5 \* 10 ^ 4，直接默写模板即可。因为使用的python语言，所以在建图的时候使用g = \[dict() for i in range(n + 1)\]，每一个g\[i\]其实是一个字典，这样可以很容易找到某条边的起点，终点以及对应的权重。

**3. 代码如下：**

from typing import List
    
    
    class Solution:
        # s表示起点, t表示终点, n表示点的个数, g为有向图
        def dijkstra(self, s: int, t: int, n: int, g: List[dict]):
            INF = 10 ** 10
            dist = [INF] * (n + 1)
            # 自己到自己的距离为0
            dist[s] = 0
            vis = [0] * (n + 1)
            # 其实循环到n - 1就可以了最后一个点对结果没有什么影响可以循环也可以不循环
            for i in range(n):
                k = -1
                # 注意节点的下标是从1开始的, 这是一个坑
                for j in range(1, n + 1):
                    # 找到当前从起点到其余点的最短距离的点的编号
                    if vis[j] == 0 and (k == -1 or dist[k] > dist[j]):
                        k = j
                vis[k] = 1
                for j in range(1, n + 1):
                    # 判断以当前的中点k是否有出边, 存在出边的时候用更新以当前的k为中间点能够到达其余点的最短距离
                    if vis[j] == 0 and j in g[k] and dist[k] + g[k][j] < dist[j]:
                        dist[j] = dist[k] + g[k][j]
            return dist[t] if dist[t] != INF else -1
    
        # dijkstra算法适用于求解边权为非负的图, 时间复杂度为O(n ^ 2)
        def process(self):
            n, m = map(int, input().split())
            # 每一个g[i]都是一个字典这样后面在找中间点k的权重的时候比较方便
            g = [dict() for i in range(n + 1)]
            for i in range(m):
                x, y, z = map(int, input().split())
                # 有向图
                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_851]: https://www.acwing.com/problem/content/description/851/