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.