网络延迟时间
题目描述:
有n个网络节点,标记为1到n。
给你一个列表times,表示信号经过有向边的传递时间。times[i] = [ui, vi, wi],其中ui是源结点,vi是目标节点,wi是一个信号从源节点传递到目标节点的时间。
现在,从某个节点K发出一个信号。需要多久才能使所有节点都收到信号?如果不能使所有节点收到信号,返回-1。
示例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
示例3:
输入:times = [[1, 2, 1]],n = 2, k = 2
输出:-1
提示:
- 1 <= k <= n <= 100
- 1 <= times.length <= 6000
- times[i].length == 3
- 1 <= ui, vi <= n
- ui != vi
- 0 <= wi <= 100
- 所有(ui, vi)对都互不相同(即,不含重复边)
思路:DFS(一般不用于最短路径求解)、BFS、Dijkstra、Bellman-Ford、Floyed等
1、DFS:建图后直接DFS递归遍历图,但是这种方法不太适合求最短路径
python代码:
class Solution:
def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
# 方法一DFS
# 建图
mp = [{} for i in range(n+1)]
for u, v, t in times:
mp[u][v] = t
# 记录结点最早收到信号的时间
current_time = [-1 for i in range(n+1)]
# DFS
def dfs(i, t):
# 在t时间到达i结点
if current_time[i] == -1 or t < current_time[i]:
current_time[i] = t
for u, v in mp[i].items():
dfs(u, t+v)
dfs(k, 0)
minT = -1
for i in range(1, n+1):
if current_time[i] == -1:
return -1
minT = max(minT, current_time[i])
return minT
2、BFS,一般最短路径都用BFS解决
python代码:
class Solution:
def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
# 方法二BFS
# 建图
mp = [{} for i in range(n+1)]
for u, v, t in times:
mp[u][v] = t
# 记录结点最早收到信号的时间
current_time = [-1 for i in range(n+1)]
current_time[k] = 0
# 队列用于存放[结点,收到信号时间]
s = deque([[k, 0]])
while s:
cur, t = s.popleft()
for u, v in mp[cur].items():
cur_t = t + v
if current_time[u] == -1 or cur_t < current_time[u]:
current_time[u] = cur_t
s.append([u, cur_t])
minT = -1
for i in range(1, n+1):
if current_time[i] == -1:
return -1
minT = max(minT, current_time[i])
return minT
3、Dijkstra,该算法为使用贪心策略优化后的广度优先搜索(BFS),缺点是不能处理存在负权的图,如果是存在负权的图,可以使用Bellman-Ford算法
python代码:
class Solution:
def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
# 方法三Dijkstra
# 建图
mp = [{} for i in range(n+1)]
for u, v, t in times:
mp[u][v] = t
# 记录结点最早收到信号的时间,设置最短路标记
r = [ float('inf') for i in range(n+1)]
s = [False for i in range(n+1)]
r[k] = 0
# 不断循环查找最短路径
while True:
# 查找最短路径
cur, t = -1, float('inf')
for i, d in enumerate(r):
if not s[i] and d < t:
cur, t = i, d
if cur == -1:
break
# 更新最短路径
s[cur] = True
for u, v in mp[cur].items():
r[u] = min(r[u], t + v)
minT = -1
for i in range(1, n+1):
minT = max(minT, r[i])
return minT if minT != float('inf') else -1