网络延迟时间

这个解决方案使用邻接矩阵来表示图，并通过一个修改版的迪杰斯特拉算法来找到从节点K到所有其他节点的最短路径。算法开始时，初始化一个距离数组，所有节点的距离设为无穷大，除了起点K，其距离设为0。然后使用一个布尔数组来跟踪每个节点的访问状态。对于每一次循环，选择一个未访问的且距离最小的节点作为当前节点，然后遍历其所有邻居，更新邻居的最短距离。这一过程重复n次，每次处理一个节点。最后，从距离数组中找出最大值，如果所有节点都已访问（即最大值不是无穷大），则返回此最大值作为结果，否则返回-1。

时间复杂度: O(n^2)

空间复杂度: O(n^2)

class Solution:
    def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
        # 使用邻接矩阵存储图
        graph = [[float('inf')] * n for _ in range(n)]
        for source, target, time in times:
            graph[source-1][target-1] = time
        
        # 初始化距离数组，所有节点到起始节点的距离设为无穷大
        distances = [float('inf')] * n
        distances[k-1] = 0  # 起始节点到自身的距离是0
        
        # 初始化访问状态数组，用于标记节点是否已被访问
        visitedNodes = [False] * n
        for _ in range(n):
            # 在未访问的节点中找到距离起始节点最近的节点
            currentNode = -1
            for neighbor, visited in enumerate(visitedNodes):
                if not visited and (currentNode == -1 or distances[neighbor] < distances[currentNode]):
                    currentNode = neighbor
            
            # 标记当前节点为已访问
            visitedNodes[currentNode] = True
            # 更新当前节点的所有未访问邻居节点的距离
            for neighbor, time in enumerate(graph[currentNode]):
                distances[neighbor] = min(distances[neighbor], distances[currentNode] + time)
        
        # 计算从起始节点到所有节点的最长最短距离
        maxDistance = max(distances)
        
        # 如果所有节点都是可达的，返回最长的最短距离；否则返回-1
        return maxDistance if maxDistance < float('inf') else -1