LeetCode 743 - 网络延迟时间

Algorithm LeetCode
August 4, 2021
中等
原题链接：https://leetcode-cn.com/problems/network-delay-time

题目描述

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

Python题解

方法一：Dijkstra 算法

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 -1python

总结

题解没看懂，debug了一遍才看懂一点，然后写了点注释 :(
增加测试用例，又debug了一遍，有了新的理解，已更新注释信息。
The End