0743. 网络延迟时间

• 标签：深度优先搜索、广度优先搜索、图、最短路、堆（优先队列）
• 难度：中等

题目链接

• 0743. 网络延迟时间 - 力扣

题目大意

描述：有 $n$ 个节点组成的网络，节点标记为 $1 \sim n$。

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

给定一个整数 $n$，表示 $n$ 个节点。

给定一个节点 $k$，表示从节点 $k$ 发出一个信号。

要求：需要多久才能使所有节点都收到信号？如果不能使所有节点收到信号，返回 $-1$。

说明：

• $1 \le k \le n \le 100$。
• $1 \le times.length \le 6000$。
• $times[i].length == 3$。
• $1 \le u_i, v_i \le n$。
• $u_i \ne v_i$。
• $0 \le w_i \le 100$。
• 所有 $(u_i, v_i)$ 对都互不相同（即不含重复边）。

示例：

• 示例 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

解题思路

思路 1：Bellman Ford 算法

思路 1：代码

class Solution:
    def bellmanFord(self, graph, n, source):
        dist = [float('inf') for _ in range(n + 1)]

        dist[source] = 0

        for i in range(n - 1):
            for vi in graph:
                for vj in graph[vi]:
                    if dist[vj] > graph[vi][vj] + dist[vi]:
                        dist[vj] = graph[vi][vj] + dist[vi]

        for vi in graph:
            for vj in graph[vi]:
                if dist[vj] > dist[vi] + graph[vi][vj]:
                    return None

        return dist

    def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
        graph = dict()
        for time in times:
            vi, vj, val = time
            if vi not in graph:
                graph[vi] = dict()
            if vj not in graph[vi]:
                graph[vi][vj] = val

        dist = self.bellmanFord(graph, n, k)

        ans = float('-inf')
        for i in range(1, len(dist)):
            ans = max(ans, dist[i])
        if ans >= float('inf'):
            return -1
        return ans

思路 1：复杂度分析

• 时间复杂度：
• 空间复杂度：

思路 2：

思路 2：代码

思路 2：复杂度分析

• 时间复杂度：
• 空间复杂度：