743. Network Delay Time 网络延迟时间

题目地址：https://leetcode.com/problems/network-delay-time/description/

题目描述：

There are N network nodes, labelled 1 to N.

Given times, a list of travel times as directed edges times[i] = (u, v, w), where u is the source node, v is the target node, and w is the time it takes for a signal to travel from source to target.

Now, we send a signal from a certain node K. How long will it take for all nodes to receive the signal? If it is impossible, return -1.

Note:

1、 Nwillbeintherange[1,100].；
2、 Kwillbeintherange[1,N].；
3、 Thelengthoftimeswillbeintherange[1,6000].；
4、 Alledgestimes[i]=(u,v,w)willhave1<=u,v<=Nand1<=w<=100.；

题目大意

求单源有向图的最长路径。如果有节点不可抵达，返回-1.

解题方法

Dijkstra算法，纯模板题。

时间复杂度是O(N ^ 2 + E)，空间复杂度是O(N+E).

代码如下：

class Solution:
    def networkDelayTime(self, times, N, K):
        """
        :type times: List[List[int]]
        :type N: int
        :type K: int
        :rtype: int
        """
        K -= 1
        nodes = collections.defaultdict(list)
        for u, v, w in times:
            nodes[u - 1].append((v - 1, w))
        dist = [float('inf')] * N
        dist[K] = 0
        done = set()
        for _ in range(N):
            smallest = min((d, i) for (i, d) in enumerate(dist) if i not in done)[1]
            for v, w in nodes[smallest]:
                if v not in done and dist[smallest] + w < dist[v]:
                    dist[v] = dist[smallest] + w
            done.add(smallest)
        return -1 if float('inf') in dist else max(dist)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

Floyd-Warshall算法。这个算法TLE.

时间复杂度O(n^3)， 空间复杂度O(n^2)。

class Solution:
    def networkDelayTime(self, times, N, K):
        """
        :type times: List[List[int]]
        :type N: int
        :type K: int
        :rtype: int
        """
        d = [[float('inf')] * N for _ in range(N)]
        for time in times:
            u, v, w = time[0] - 1, time[1] - 1, time[2]
            d[u][v] = w
        for i in range(N):
            d[i][i] = 0
        for k in range(N):
            for i in range(N):
                for j in range(N):
                    d[i][j] = min(d[i][j], d[i][k] + d[k][j])
        return -1 if float('inf') in d[K - 1] else max(d[K - 1])

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

Bellman-Ford算法，这个算法TLE。

时间复杂度O(ne)， 空间复杂度O(n)。

class Solution:
    def networkDelayTime(self, times, N, K):
        """
        :type times: List[List[int]]
        :type N: int
        :type K: int
        :rtype: int
        """
        dist = [float('inf')] * N
        dist[K - 1] = 0
        for i in range(N):
            for time in times:
                u = time[0] - 1
                v = time[1] - 1
                w = time[2]
                dist[v] = min(dist[v], dist[u] + w)
        return -1 if float('inf') in dist else max(dist)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

参考资料：

https://zxi.mytechroad.com/blog/graph/leetcode-743-network-delay-time/ https://leetcode.com/problems/network-delay-time/discuss/172857/Python-Dijkstra-Solution-that-beats-86

DDKK.COM 弟弟快看-教程，程序员编程资料站，版权归原作者所有

本文经作者：负雪明烛 授权发布，任何组织或个人未经作者授权不得转发