743 网络延迟时间（单源最短路径-spfa/dijkstra）

傷城~ 2022-09-10 08:28 126阅读 0赞

**1. 问题描述：**

有 n 个网络节点，标记为 1 到 n。给你一个列表 times，表示信号经过有向边的传递时。 times\[i\] = (ui,，vi， wi)，其中 ui 是源节点，vi 是目标节点， wi 是一个信号从源节点传递到目标节点的时间。现在，从某个节点 K 发出一个信号。需要多久才能使所有节点都收到信号？如果不能使所有节点收到信号，返回 -1 。

**示例 1：**

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeXV6aGFuZ196eQ_size_7_color_FFFFFF_t_70_g_se_x_16][]

输入：times = \[\[2,1,1\],\[2,3,1\],\[3,4,1\]\], n = 4, k = 2  
输出：2

**示例 2：**

输入：times = \[\[1,2,1\]\], n = 2, k = 1  
输出：1

**示例 3：**

输入：times = \[\[1,2,1\]\], n = 2, k = 2  
输出：-1

**提示：**

1 <= k <= n <= 100  
1 <= times.length <= 6000  
times\[i\].length == 3  
1 <= ui, vi <= n  
ui != vi  
0 <= wi <= 100  
所有 (ui, vi) 对都互不相同（即不含重复边）  
来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/network-delay-time

**2. 思路分析：**

分析题目可以知道我们需要求解从源点到达其余顶点的最短距离，然后在这些最短距离中取一个max表示从源点到其余顶点的最大距离，所以可以知道这道题目其实是**单源最短路径**的裸题，对于单源最短路径的问题可以使用spfa或者是dijkstra算法求解，因为使用的是python语言所以在建图（建图的目的是为了能够从下标访问有联系的顶点）的时候可以声明一个列表g，列表的每一个元素为字典类型，这样g列表相于是一个邻接表，访问元素会比较方便（或者是使用collections.defaultdict(list)声明一个字典，字典的每一个元素为list列表类型，我们可以将当前边的终点以及权重作为元组添加到列表对应的字典中）。

**3. 代码如下：**

**spfa模板：**

from typing import List
    import collections
    
    
    class Solution:
        def spfa(self, times: List[List[int]], n: int, k: int):
            INF = 10 ** 9
            dist = [INF] * (n + 1)
            dist[k] = 0
            # 列表的每一个元素为一个字典, 这样g相当于是一个邻接表
            g = [dict() for i in range(n + 1)]
            for x in times:
                start, end, time = x[0], x[1], x[2]
                # 存储起点到终点的权重, 有的题目存在重边的情况这道题目没有所以就不用判断了取最小的那条边的情况
                g[start][end] = time
            # is_used用来记录队列中是否存在当前的元素
            is_used = [0] * (n + 1)
            is_used[k] = 1
            q = collections.deque([k])
            while q:
                poll = q.popleft()
                is_used[poll] = 0
                # g[poll]为字典
                for k, v in g[poll].items():
                    # k表示边的终点, v表示边的权重, 更新对应的dist位置的值
                    if dist[k] > v + dist[poll]:
                        dist[k] = v + dist[poll]
                        if is_used[k] == 0:
                            is_used[k] = 1
                            q.append(k)
    
            res = 0
            for i in range(1, n + 1):
                # 求解出从源点到其余顶点的最大距离
                res = max(res, dist[i])
            return res if res != INF else -1
    
        def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
            return self.spfa(times, n, k)

除了上面建图的方法之外，我们也可以将g声明为字典类型，每一个字典为list类型，list列表中的元素为元组类型，这样就可以将当前边的终点以及权重作为元组的元素加入到当前的列表中：

from typing import List
    import collections
    
    
    class Solution:
        def spfa(self, times: List[List[int]], n: int, k: int):
            INF = 10 ** 9
            # 初始化距离列表, 节点编号从1开始所以需要多声明一个长度
            dist = [INF] * (n + 1)
            # 自身的距离为0
            dist[k] = 0
            g = collections.defaultdict(list)
            # 建图
            for x in times:
                start, end, time = x[0], x[1], x[2]
                # 添加对应的边以及权重, 将其作为元组类型添加到g[start]中
                g[start].append((end, time))
            is_used = [0] * (n + 1)
            is_used[k] = 1
            q = collections.deque([k])
            while q:
                poll = q.popleft()
                # 弹出队列中的节点之后需要将其标记为未访问
                is_used[poll] = 0
                for x in g[poll]:
                    if dist[x[0]] > dist[poll] + x[1]:
                        dist[x[0]] = dist[poll] + x[1]
                        if is_used[x[0]] == 0:
                            is_used[x[0]] = 1
                            q.append(x[0])
            res = 0
            for i in range(1, n + 1):
                res = max(res, dist[i])
            return res if res != INF else -1
    
        def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
            return self.spfa(times, n, k)

**dijkstra模板：**

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]
            res = 0
            for i in range(1, n + 1):
                res = max(res, dist[i])
            return res if res != INF else -1
    
        def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
            return self.dijkstra(times, n, k)

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeXV6aGFuZ196eQ_size_7_color_FFFFFF_t_70_g_se_x_16]: /images/20220829/76ab2ddcf9f84d3fa02a0197ea0d9aa1.png