Chương trình tìm ra đường đi giữa hai đỉnh trong biểu đồ có hình phạt tối thiểu (Python)

Giả sử chúng ta được cung cấp một đồ thị vô hướng, có trọng số và được yêu cầu tìm ra con đường có hình phạt nhỏ nhất có thể từ nút a đến nút b. Hình phạt của một đường dẫn là OR theo chiều dọc bit của trọng số của tất cả các cạnh trong đường dẫn. Vì vậy, chúng ta phải tìm ra một đường dẫn 'hình phạt tối thiểu' như vậy và nếu không có đường đi nào giữa hai nút, chúng ta trả về -1.

Vì vậy, nếu đầu vào giống như

start (s) =1, end (e) =3; thì đầu ra sẽ là 15.

Tồn tại hai con đường giữa các đỉnh 1 và 3. Con đường tối ưu là 1-> 2-> 3, chi phí của con đường là (10 OR 5) =15.

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

• Xác định một hàm trợ giúp (). Điều này sẽ lấy G, s, e
  • v:=một tập hợp mới
  • c:=một danh sách mới có kích thước n được khởi tạo với giá trị vô cực
  • heap:=heap mới chứa cặp (0, s)
  • trong khi kích thước của heap> 0, thực hiện
    • cst:=bật mục nhỏ nhất khỏi đống
    • cur:=bật mục nhỏ nhất khỏi đống
    • c [cur]:=tối thiểu là (cst, c [cur])
    • if (cst, cur) có trong v, thì
      • chuyển sang lần lặp tiếp theo
    • nếu cur giống với e, thì
      • trả về c [cur]
    • thêm cặp (cst, cur) vào v
    • đối với mỗi người hàng xóm, n_cost trong G [cur], thực hiện
      • đẩy các giá trị ((n_cost HOẶC cst), hàng xóm) vào heap
  • trả lại c [e]
• G:=[danh sách mới chứa n + 1 danh sách biểu tượng]
• đối với mỗi mục trong các cạnh, thực hiện
  • u:=item [0]
  • v:=item [1]
  • w:=item [2]
  • chèn cặp (v, w) vào cuối G [u]
  • chèn cặp (u, w) vào cuối G [v]
• ans:=helper (G, s, e)
• trả về -1 nếu ans giống với inf, ngược lại trả về ans

Ví dụ

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

import heapq
from math import inf

def helper(G, s, e):
    v = set()
    c = [inf] * len(G)
    heap = [(0, s)]
    while len(heap) > 0:
        cst, cur = heapq.heappop(heap)
        c[cur] = min(cst, c[cur])
        if (cst, cur) in v:
            continue
        if cur == e:
            return c[cur]
        v.add((cst, cur))
        for neighbor, n_cost in G[cur]:
            heapq.heappush(heap, (n_cost | cst, neighbor))
    return c[e]

def solve(n, edges, s, e):
    G = [[] for _ in range(n + 1)]
    for item in edges:
        u, v, w = map(int, item)
        G[u].append((v, w))
        G[v].append((u, w))
    ans = helper(G, s, e)
    return -1 if ans == inf else ans

print(solve(4, [(1, 2, 10), (2, 3, 5), (2, 4, 15), (1, 4, 20)], 1, 3))

Đầu vào

4, [(1, 2, 10), (2, 3, 5), (2, 4, 15), (1, 4, 20)], 1, 3

Đầu ra

15