โปรแกรมค้นหาว่าจะใช้เวลานานเท่าใดในการเข้าถึงข้อความในเครือข่ายใน Python

สมมติว่าเรามีตัวเลขและรายการขอบ n โหนดต่างๆ เหล่านี้มีป้ายกำกับว่า 0 ถึง N โหนดเหล่านี้กำลังสร้างเครือข่าย แต่ละขอบอยู่ในรูปแบบ (a, b, t) ของกราฟที่ไม่มีทิศทาง ซึ่งแสดงว่าเราพยายามส่งข้อความจาก a ถึง b หรือ b ไปยัง a จะใช้เวลา t เมื่อโหนดได้รับข้อความ ข้อความจะท่วมไปยังโหนดที่อยู่ใกล้เคียงทันที หากโหนดทั้งหมดเชื่อมต่อกัน เราต้องหาว่าจะใช้เวลานานแค่ไหนกว่าที่ทุกโหนดจะได้รับข้อความที่เริ่มต้นที่โหนด 0

ดังนั้น หากอินพุตเป็น n =3 edge =[[0, 1, 3],[1, 2, 4],[2, 3, 2]] ผลลัพธ์จะเป็น 9 เป็นโหนดที่ 4 ( โหนดหมายเลข 3) ได้รับข้อความจาก 0 -> 1 -> 2 -> 3 ซึ่งใช้เวลา 3 + 4 + 2 =9 จำนวน

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

กำหนดฟังก์ชัน build_graph() นี้จะเป็นขอบ

• กราฟ :=แผนที่ว่างเปล่า
• สำหรับแต่ละ (src, dest, t) ที่ตั้งค่าเป็นขอบ ทำ
  • แทรก (dest, t) ลงในกราฟ[src]
  • แทรก (src, t) ลงในกราฟ[dest]
• กราฟผลตอบแทน
• จากวิธีหลัก ให้ทำดังนี้ -
• กราฟ :=build_graph(ขอบ)
• เข้าชมแล้ว :=ชุดใหม่
• heap :=สร้างฮีปใหม่ด้วยคู่ (0, 0)
• ในขณะที่ฮีปไม่ว่าง ให้ทำ
  • (current_total_time, node) :=องค์ประกอบด้านบนของ heap และลบออกจาก heap
  • ทำเครื่องหมายโหนดว่าเข้าชมแล้ว
  • ถ้าจำนวนโหนดที่เข้าชมเท่ากับ (n + 1) ดังนั้น
    • ส่งคืน current_total_time
  • สำหรับแต่ละคู่ (nei, เวลา) ใน graph[node], do
    • ถ้าเน่ไม่ได้มาก็
      • แทรกคู่ (current_total_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