Chương trình tìm xem mất bao lâu để truy cập các thông báo trong một mạng bằng Python

Giả sử chúng ta có một số và danh sách các cạnh. N nút khác nhau này được gắn nhãn từ 0 đến N. Các nút này đang tạo thành một mạng. Mỗi cạnh ở dạng (a, b, t) của một đồ thị vô hướng, điều này thể hiện nếu chúng ta cố gắng gửi thông điệp từ a đến b hoặc b đến a, sẽ mất t thời gian. Khi một nút nhận được một thông báo, nó ngay lập tức chuyển thông báo đó sang một nút lân cận. Nếu tất cả các nút được kết nối, chúng ta phải tìm xem sẽ mất bao lâu để mọi nút nhận được thông báo bắt đầu từ nút 0.

Vì vậy, nếu đầu vào là n =3 cạnh =[[0, 1, 3], [1, 2, 4], [2, 3, 2]], thì đầu ra sẽ là 9, là nút thứ 4 ( nút số 3) nhận thông báo từ 0 -> 1 -> 2 -> 3, mất 3 + 4 + 2 =9 lượng thời gian.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

Định nghĩa một hàm build_graph (). Điều này sẽ có lợi ích

graph:=một bản đồ trống
đối với mỗi (src, dest, t) được đặt trong các cạnh, thực hiện
- chèn (đích, t) vào biểu đồ [src]
- chèn (src, t) vào biểu đồ [dest]
biểu đồ trả về
Từ phương thức chính, hãy làm như sau -
đồ thị:=build_graph (các cạnh)
đã thăm:=một tập hợp mới
heap:=tạo một heap mới với cặp (0, 0)
trong khi heap không trống, hãy thực hiện
- (current_total_time, node):=phần tử trên cùng của heap và xóa nó khỏi heap
- đánh dấu nút là đã truy cập
- nếu số lượng các nút đã truy cập bằng (n + 1), thì
  - trả về current_total_time
- đối với mỗi cặp (nei, thời gian) trong biểu đồ [node], thực hiện
  - nếu nei không được truy cập, thì
    - chèn cặp (current_total_time + time, nei) vào heap

Ví dụ (Python)

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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))

Đầu vào

3, [[0, 1, 3],[1, 2, 4],[2, 3, 2]]