问题描述

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

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

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

在这里插入图片描述
输入：times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2
输出：2

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/network-delay-time

迪杰斯特拉方法实现示意图（dijkstra）

在这里插入图片描述

代码实现

class Solution:
    def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
        dic = generateGraph(times)
        if k not in dic:return -1
        dist = SP(dic, k, n)
        ans = -1 if max(dist[1:]) == float('inf') else max(dist[1:])
        return ans
'''
最短路径
迪杰斯特拉方法实现 （dijkstra）
'''
def SP(dic,u,n):
    visited = [False for i in range(n+1)]
    dist = [float('inf') for i in range(n+1)]
    dist[u] = 0
    for v1 in dic[u]:
        dist[v1]=dic[u][v1]
    while True:
        v = -1
        for i in range(n+1): # 找没有处理过的结点v且距离u最近的点
            if visited[i]: continue
            if v<0 or dist[v]>dist[i]:v=i
        if v<0:return dist
        visited[v] = True
        if v not in dic:continue
        for v1 in dic[v]: # 找v的邻结点b 根据三角不等式计算结果，取 u-v-b 和u-b二者最小值作为u到b的距离，
            if visited[v1]:continue
            if dist[v]+dic[v][v1]<dist[v1]:dist[v1] = dist[v]+dic[v][v1]
def generateGraph(times):
    dic = {}
    for u,v,i in times:
        if u not in dic:dic[u] ={}
        dic[u][v]=i
    return dic