Python程序：查找网络中消息到达所需时间

假设我们有一个数字和一个边的列表。这些 n 个不同的节点标记为 0 到 N。这些节点构成一个网络。每条边都以 (a, b, t) 的形式表示无向图，这表示如果我们尝试从 a 发送消息到 b 或从 b 发送消息到 a，则需要 t 时间。当一个节点接收到消息时，它会立即将消息洪泛到相邻节点。如果所有节点都连接，我们必须找到从节点 0 开始的消息到达每个节点需要多长时间。

因此，如果输入类似于 n = 3 edges = [[0, 1, 3],[1, 2, 4],[2, 3, 2]]，则输出将为 9，因为第 4 个节点（节点编号 3）从 0 -> 1 -> 2 -> 3 接收消息，这需要 3 + 4 + 2 = 9 的时间。

为了解决这个问题，我们将遵循以下步骤：

定义一个函数 build_graph()。这将接收边作为输入。

  • graph := 一个空映射
  • 对于 edges 中的每个 (src, dest, t) 集合，执行以下操作：
    • 将 (dest, t) 插入到 graph[src] 中
    • 将 (src, t) 插入到 graph[dest] 中
  • 返回 graph
  • 从主方法执行以下操作：
  • graph := build_graph(edges)
  • visited := 一个新的集合
  • heap := 创建一个新的堆，包含 (0, 0) 对
  • 当堆不为空时，执行以下操作：
    • (current_total_time, node) := 堆的顶部元素，并将其从堆中删除
    • 标记节点为已访问
    • 如果已访问节点的数量与 (n + 1) 相同，则
      • 返回 current_total_time
    • 对于 graph[node] 中的每个 (nei, time) 对，执行以下操作：
      • 如果 nei 未被访问，则
        • 将 (current_total_time + time, nei) 对插入到堆中

示例（Python）

让我们看看以下实现以更好地理解：

 在线演示

import heapq
from collections import defaultdict
class Solution:
   def solve(self, n, edges):
      graph = self.build_graph(edges)  
      visited = set()
      heap = [(0, 0)]
      while heap:
         current_total_time, node = heapq.heappop(heap)
         visited.add(node)  
         if len(visited) == (n + 1):
            return current_total_time
         for nei, time in graph[node]:
            if nei not in visited:
               heapq.heappush(heap, (current_total_time + time, nei))
   def build_graph(self, edges):
      graph = defaultdict(set)
      for src, dest, t in edges:
         graph[src].add((dest, t))
         graph[dest].add((src, t))
      return graph
ob = Solution()
n = 3
edges = [[0, 1, 3],[1, 2, 4],[2, 3, 2]]
print(ob.solve(n, edges))

输入

3, [[0, 1, 3],[1, 2, 4],[2, 3, 2]]

输入

9

更新时间： 2020年12月12日

125 次查看

开启您的 职业生涯

通过完成课程获得认证

开始学习
广告

© . All rights reserved.