难度：★★★★☆
类型：图
方法：深度优先搜索

力扣链接请移步本题传送门
更多力扣中等题的解决方案请移步力扣中等题目录

题目

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

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

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

例如：
输入：
times = [[2, 1, 1], [2, 3, 1], [3, 4, 1]]
N = 4
K = 2
输入：2

解答

我们常常会使用深度优先搜索来解决图的遍历问题。

【图的定义】
这个问题很实际，首先需要留意一下题目给出的输入方式，有必要先搞清楚题目中的图是怎么构建的。根据题意，题目中所给出的图是一张有向图，并且结点与结点之间的每个连接是有权值的。为了便于表示，我们用一个哈希字典来表达这张图。

在下面的代码中，这张图的变量名为node_to_nodes，顾名思义，字典的键是所有结点的编号，字典的值是一个个列表，列表中表示的是结点node的下一跳结点next_node，这里需要注意，我们把该结点next_node以及从结点node到next_node所需要的耗时time_cost打包成了一个元组了，这样保留了连接耗时的信息。我们很容易发现，每个作为字典键的结点一定不是末尾结点（或者理解成树的叶子节点，虽然并不严谨）。

【深度优先搜索】

我们需要知道到达每个结点的时间，定义一个哈希字典node_to_elapsed，用来表达每个结点以及从信息最开始发送的结点到达这个结点所需要的最短耗时，耗时需要初始化为无穷，以备迭代和最终判断需要。

定义深度优先搜索函数，该函数接收两个输入，即图中的任意一个结点node以及到达该结点的总耗时elapsed_time，这个耗时是根据上一跳结点及其到达本结点的时间计算的。在递归函数内部，需要执行以下操作：

1. 根据node_to_elapsed字典，更新一下当前结点处的总耗时；
2. 根据node_to_nodes字典，寻找当前结点node的所有下一跳结点，根据当前节点总耗时elapsed_time及连接耗时time，计算下一跳节点的总耗时next_elapsed_time，
3. 判断下一跳结点next_node的总耗时是否比当前在耗时字典node_to_elapsed中存储的值更小，如果是，则递归进行迭代。这一步判断的意义在于，处理多个结点指向同一个结点的情况，需要取可以使该结点总耗时最小的路线。

最后，耗时字典node_to_elapsed中就存储了信号到达所有节点需要的最短耗时，选择其中最大的即可作为整个网络收到信号的最短时间，注意如果存在无法达到的结点，那么该结点处耗时为初始化的无穷大。

import collections
class Solution(object):
    def networkDelayTime(self, times, N, K):
        node_to_nodes = collections.defaultdict(list)
        for node, next_node, time_cost in times:
            node_to_nodes[node].append((next_node, time_cost))

        node_to_elapsed = {node: float('inf') for node in range(1, N+1)}

        def dfs(node, elapsed_time):
            node_to_elapsed[node] = elapsed_time
            for next_node, time in node_to_nodes[node]:
                next_elapsed_time = elapsed_time + time
                if next_elapsed_time < node_to_elapsed[next_node]:
                    dfs(next_node, next_elapsed_time)

        dfs(K, 0)
        ans = max(node_to_elapsed.values())
        return ans if ans < float('inf') else -1

如有疑问或建议，欢迎评论区留言~

有关更多力扣中等题的python解决方案，请移步力扣中等题解析