Chương trình tìm ra chi phí tối thiểu có thể có từ đồ thị có trọng số bằng Python

Giả sử chúng ta có một danh sách 2D các số nguyên được gọi là các cạnh là biểu diễn của một đồ thị vô hướng. Mọi hàng trong đầu vào đại diện cho một cạnh [u, v, w] nghĩa là các nút u và v được nối với nhau và cạnh đó có trọng số w. Biểu đồ bao gồm n nút từ 0 đến n-1.

Chi phí của một đường dẫn ở đây được định nghĩa là tích của số cạnh và trọng số tối đa cho bất kỳ cạnh nào trong đường dẫn. Chúng tôi phải tìm ra chi phí tối thiểu có thể từ nút 0 đến nút n-1, hoặc chúng tôi tuyên bố câu trả lời là -1 nếu không có đường dẫn nào như vậy tồn tại.

So, if the input is like edges = [
   [0, 2, 100],
   [1, 2, 200],
   [1, 3, 100],
   [2, 3, 300]
], then the output will be 600

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

• graph:=a new map

• weights:=một bản đồ mới

• max_weight:=0

• N:=0

• đối với mỗi u, v, w trong các cạnh, làm

  • chèn v vào cuối biểu đồ [u]

  • chèn u vào cuối biểu đồ [v]

  • trọng số [u, v]:=w

  • trọng số [v, u]:=w

  • N:=tối đa N, u + 1, v + 1

  • max_weight:=tối đa của max_weight, w

• kết quả:=infinity

• trong khi max_weight> =0, thực hiện

  • d, weight:=bfs (0, max_weight)

  • nếu d> =0, thì

    • result:=tối thiểu của kết quả, d * trọng số

    • max_weight:=weight - 1

  • nếu không,

    • chấm dứt vòng lặp

• trả về kết quả nếu kết quả

• Định nghĩa một hàm bfs (). Điều này sẽ bắt nguồn từ root, weight_cap

  • target:=N - 1

  • Q:=a deque chứa root, 0, 0

  • đã truy cập:=[False] * N

  • đã ghé thăm [0]:=True

  • trong khi Q không trống, thực hiện

    • v, d, current_weight:=xóa phần tử cuối cùng khỏi Q

    • nếu v giống N - 1 thì

      • trả về d, current_weight

    • đối với mỗi w trong biểu đồ [v], thực hiện

      • nếu đã thăm [w] khác 0 thì

        • tiếp tục lần lặp tiếp theo

      • new_weight:=weights [v, w]

      • nếu new_weight <=weight_cap thì

        • đã ghé thăm [w]:=True

        • thêm (w, d + 1, tối đa là (current_weight, new_weight)) ở bên trái Q

  • trả về -1, -1

Ví dụ

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

from collections import defaultdict, deque
class Solution:
   def solve(self, edges):
      graph = defaultdict(list)
      weights = {}
      max_weight = 0
      N = 0
      for u, v, w in edges:
         graph[u].append(v)
         graph[v].append(u)
         weights[u, v] = w
         weights[v, u] = w
         N = max(N, u + 1, v + 1)
         max_weight = max(max_weight, w)
      def bfs(root, weight_cap):
         target = N - 1
         Q = deque([(root, 0, 0)])
         visited = [False] * N
         visited[0] = True
         while Q:
            v, d, current_weight = Q.pop()
            if v == N - 1:
               return d, current_weight
            for w in graph[v]:
               if visited[w]:
                  continue
               new_weight = weights[v, w]
               if new_weight <= weight_cap:
                  visited[w] = True
                     zQ.appendleft((w, d + 1, max(current_weight, new_weight)))
         return -1, -1
      result = float("inf")
      while max_weight >= 0:
         d, weight = bfs(0, max_weight)
         if d >= 0:
            result = min(result, d * weight)
            max_weight = weight - 1
         else:
            break
      return result if result < float("inf") else -1

ob = Solution()
print (ob.solve( [
   [0, 2, 100],
   [1, 2, 200],
   [1, 3, 100],
   [2, 3, 300]
]))

Đầu vào

[
   [0, 2, 100],
   [1, 2, 200],
   [1, 3, 100],
   [2, 3, 300]
]

Đầu ra

600