Dijkstrk算法朴素板

桃扇骨 2022-09-10 08:22 41阅读 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

**输出样例：**

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

**2. 思路分析：**

dijkstra算法求解**单源最短路径**问题（spfa算法也可以求解单源最短路径问题），也即求解从一个点到其余点的最短距离，dijkstra算法的思想其实也比较容易理解，首先我们需要找到dist数组或者列表中最短的边对应的点并且这个点之前是没有访问过的，然后从这个点出发，找到对应的出边，更新出边对应的dist位置，一直循环这个过程直到所有的顶点都已经被访问过了就停止了，此时dist数组或者列表存储的就是从源点到其余点的最短距离。因为使用的是python语言所以我们在建图的时候可以声明一个长度为n的列表dist，列表中的每一个元素为一个字典，这样dist就相当于是一个邻接表了。

**3. 代码如下：**

**python：**

from typing import List
    
    
    class Solution:
        # k表示起点, n表示节点个数
        def dijkstra(self, nums: List[List[int]], n: int, k: int):
            # g中每一个元素都是一个字典, 这样相当于是一个邻接表, 下面这样声明比直接声明一个二维列表的耗时要短, python初始化一个长度比较大的列表的时候耗时很大
            g = [dict() for i in range(n + 1)]
            # 建图
            for x in nums:
                start, end, weight = x[0], x[1], x[2]
                # 这里有一个坑是一个点到另外一个点可能存在重复的边这个时候需要取最小的那条边
                if end in g[start]: g[start][end] = min(g[start][end], weight)
                else: g[start][end] = weight
            INF = 10 ** 10
            dist = [INF] * (n + 1)
            dist[k] = 0
            vis = [0] * (n + 1)
            for i in range(n):
                k = -1
                # _min表示当前最小值
                _min = INF
                # 使用循环找到当前距离最小的那个顶点
                for j in range(1, n + 1):
                    if vis[j] == 0 and _min > dist[j]:
                        k = j
                        _min = dist[j]
                # 不存在没有更新的顶点就可以break了
                if k == -1: break
                vis[k] = 1
                for j in range(1, n + 1):
                    # 由当前的点更新到其余点的最短距离
                    if vis[j] == 0 and j in g[k] and dist[j] > dist[k] + g[k][j]:
                        dist[j] = dist[k] + g[k][j]
            return dist[n] if dist[n] != INF else -1
    
    
    if __name__ == "__main__":
        # n表示节点数量, m表示边长
        n, m = map(int, input().split())
        nums = list()
        for i in range(m):
            start, end, weight = map(int, input().split())
            nums.append([start, end, weight])
        print(Solution().dijkstra(nums, n, 1))

[https_www.acwing.com_problem_content_851]: https://www.acwing.com/problem/content/851/