力扣每日一题21.08.02网络延迟时间

网络延迟时间

题目描述:

有n个网络节点,标记为1到n。

给你一个列表times,表示信号经过有向边的传递时间。times[i] = [ui, vi, wi],其中ui是源结点,vi是目标节点,wi是一个信号从源节点传递到目标节点的时间。

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

示例1:

力扣每日一题21.08.02网络延迟时间

输入: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代码:

力扣每日一题21.08.02网络延迟时间

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代码:

力扣每日一题21.08.02网络延迟时间

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代码:

力扣每日一题21.08.02网络延迟时间

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

上一篇:Java 开发 2.0: Kilim 简介


下一篇:使用PowerShell查找Office365&Exchange2013-16的邮箱大小