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

假设我们有一个数字和边的列表。这些n个不同的节点标记为0到N。这些节点形成一个网络。每个边以无向图的形式表示为（a，b，t），这表示如果我们尝试从a或b发送消息，则需要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（）函数。这将采用边缘

图：一个空map
对于每个（src，dest，t）集合中的边缘，请执行以下操作
- 在graph [src]中插入（dest，t）
- 在graph [dest]中插入（src，t）
返回图
从主方法执行以下操作 –
图：build_graph（edges）
已访问：一个新的集合
堆：使用对（0，0）进行新堆制作
while堆不为空，请执行以下操作
- （current_total_time，node）：堆的顶部元素，并从堆中删除它
- 标记节点已访问
- 如果访问的节点数与（n + 1）相同，则
  - 返回current_total_time
- 对于图[node]中的每对（nei，time），请执行以下操作
  - 如果邻居没有访问过，则
  - 将pair（current_total_time + time，nei）插入堆中

更多Python相关文章，请阅读：Python 教程

示例（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))