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.
Example 1:
Input: times = [[2,1,1],[2,3,1],[3,4,1]], N = 4, K = 2
Output: 2
Note:
- N will be in the range [1, 100].
- K will be in the range [1, N].
- The length of times will be in the range [1, 6000].
- All edges times[i] = (u, v, w) will have 1 <= u, v <= N and 0 <= w <= 100.
Solutions
1. Dijkstras’s algorithm
2. Bellman-Ford
说是模板题，得用上 DP。
class Solution:
def networkDelayTime(self, times: List[List[int]], N: int, K: int) -> int:
dist = [float('inf') for _ in range(N)]
dist[K-1] = 0
for i in range(N):
for time in times:
u, v, w = time[0] - 1, time[1] - 1, time[2]
dist[v] = min(dist[v], dist[u]+w)
max_dist = max(dist)
return -1 if max_dist == float('inf') else max_dist
# Runtime: 2064 ms, faster than 5.05% of Python3 online submissions for Network Delay Time.
# Memory Usage: 15.5 MB, less than 7.69% of Python3 online submissions for Network Delay Time.
3. Floyd-Warshall (all pairs)
三维的 DP：
class Solution:
def networkDelayTime(self, times: List[List[int]], N: int, K: int) -> int:
dist = [[float('inf') for _ in range(N)] for _ in range(N)]
for time in times:
dist[time[0]-1][time[1]-1] = time[2]
for i in range(N):
dist[i][i] = 0
# pay attention to this order k, i, j
for k in range(N):
for i in range(N):
for j in range(N):
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
max_dist = max(dist[K-1])
return -1 if max_dist == float('inf') else max_dist
# Runtime: 1884 ms, faster than 5.05% of Python3 online submissions for Network Delay Time.
# Memory Usage: 15.6 MB, less than 7.69% of Python3 online submissions for Network Delay Time.