Pythonのネットワークでメッセージに到達するのにかかる時間を見つけるためのプログラム

エッジの数とリストがあるとします。 0からNのラベルが付いたこれらのn個の異なるノード。これらのノードはネットワークを形成しています。各エッジは無向グラフの形式（a、b、t）であり、これは、メッセージをaからbまたはbからaに送信しようとすると、t時間かかることを表しています。ノードがメッセージを受信すると、すぐにそのメッセージを隣接ノードにフラッディングします。すべてのノードが接続されている場合、すべてのノードがノード0から始まるメッセージを受信するのにかかる時間を見つける必要があります。

したがって、入力がn =3エッジ=[[0、1、3]、[1、2、4]、[2、3、2]]の場合、出力は4番目のノードとして9になります（ノード番号3）は、0-> 1->2->3からメッセージを受信します。これには3+4 + 2=9の時間がかかります。

これを解決するには、次の手順に従います-

関数build_graph（）を定義します。これはエッジを取ります

• グラフ：=空の地図
• エッジに設定された（src、dest、t）ごとに、
  • グラフに（dest、t）を挿入[src]
  • グラフに（src、t）を挿入[宛先]
• リターングラフ
• メインメソッドから次の手順を実行します-
• グラフ：=build_graph（edges）
• 訪問：=新しいセット
• ヒープ：=ペア（0、0）で新しいヒープを作成します
• ヒープが空でない間は、
  • （current_total_time、node）：=ヒープの最上位要素であり、ヒープから削除します
  • ノードを訪問済みとしてマーク
  • 訪問したノードの数が（n + 1）と同じ場合、
    • return current_total_time
  • グラフ[ノード]の各ペア（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