LeetCode 743 - 网络延迟时间

中等

原题链接：https://leetcode-cn.com/problems/network-delay-time (opens new window)

题目描述

有 n 个网络节点，标记为 1 到 n。

给你一个列表 times，表示信号经过 有向 边的传递时间。 times[i] = (ui, vi, wi)，其中 ui 是源节点，vi 是目标节点， wi 是一个信号从源节点传递到目标节点的时间。

现在，从某个节点 K 发出一个信号。需要多久才能使所有节点都收到信号？如果不能使所有节点收到信号，返回 -1 。

示例 1

输入：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) 对都 互不相同（即，不含重复边）

Python题解

方法一：Dijkstra 算法

Dijkstra 算法

迪杰斯特拉算法(Dijkstra)是由荷兰计算机科学家狄克斯特拉于1959年提出的，因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法，解决的是有权图中最短路径问题。迪杰斯特拉算法主要特点是从起始点开始，采用贪心算法的策略，每次遍历到始点距离最近且未访问过的顶点的邻接节点，直到扩展到终点为止。

    def networkDelayTime(self, times, n, k):
        """
        :type times: List[List[int]]
        :type n: int
        :type k: int
        :rtype: int
        """
        # 邻接矩阵存储图，此处存储距离信息
        g = [[float('inf')] * n for _ in range(n)]
        # 从邻接矩阵更新权重，对下标进行了减一处理
        for start, end, time in times:
            g[start - 1][end - 1] = time
        # 目标节点到其他节点的最短距离列表信息
        distance = [float('inf')] * n
        # 起点距离设置为0
        distance[k - 1] = 0
        # 用于标记已被经过的节点
        used = [False] * n
        # 遍历所有节点
        for _ in range(n):
            # 第一次不用比较距离用到的参数
            x = -1
            # 获取未被标记的最近节点
            for index, false in enumerate(used):
                if not false and (x == -1 or distance[index] < distance[x]):
                    x = index
            # 标记节点
            used[x] = True
            # 更新最短路径距离
            for index, time in enumerate(g[x]):
                distance[index] = min(distance[index], distance[x] + time)
        # 要求所有节点接收，所以返回最短距离的最大值
        ans = max(distance)
        # 如果存在inf则代表有节点不可达，此时返回-1
        return ans if ans < float('inf') else -1

总结

题解没看懂，debug了一遍才看懂一点，然后写了点注释 😦

增加测试用例，又debug了一遍，有了新的理解，已更新注释信息。