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

สมมติว่าเรามีตัวเลข n และรายการเส้นเชื่อม edges มีโหนด 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

ขั้นตอนการแก้ปัญหา (Dijkstra / Minimum Spanning Tree)

• สร้างกราฟจาก edges: graph[src].add((dest, t)) และ graph[dest].add((src, t))
• visited := set(), heap := [(0, 0)] (เวลา, โหนด)
• while heap ไม่ว่าง:
  • ดึง (current_total_time, node) จาก heap
  • mark node visited
  • ถ้า len(visited) == n+1 คืน current_total_time
  • วนเพื่อนบ้าน (nei, time) ของ node:
    • ถ้า nei ยังไม่ visited: push (current_total_time + time, nei) เข้า heap

ตัวอย่างโค้ด

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