โปรแกรมหาเส้นทางระหว่างจุดยอดสองจุดในกราฟที่มีโทษขั้นต่ำ (Python)

สมมติว่าเราได้รับกราฟที่ไม่มีทิศทางและมีการถ่วงน้ำหนัก และถูกขอให้ค้นหาเส้นทางโดยมีค่าปรับขั้นต่ำที่เป็นไปได้จากโหนด a ไปยังโหนด b บทลงโทษของเส้นทางคือค่า OR ระดับบิตของน้ำหนักของขอบทั้งหมดในเส้นทาง ดังนั้น เราต้องค้นหาเส้นทาง 'การลงโทษขั้นต่ำ' ดังกล่าว และหากไม่มีเส้นทางระหว่างโหนดทั้งสอง เราจะคืนค่า -1

ดังนั้นหากอินพุตเป็นแบบ

เริ่ม (s) =1 สิ้นสุด (e) =3; แล้วผลลัพธ์จะเป็น 15

มีสองเส้นทางระหว่างจุดยอด 1 และ 3 เส้นทางที่เหมาะสมคือ 1->2->3 ราคาของเส้นทางคือ (10 หรือ 5) =15

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

• กำหนดฟังก์ชัน helper() นี่จะใช้เวลา G, s, e
  • v :=ชุดใหม่
  • c :=รายการใหม่ของขนาด n เริ่มต้นด้วยค่าอินฟินิตี้
  • ฮีป :=ฮีปใหม่ที่มีคู่ (0, s)
  • ในขณะที่ขนาดของฮีป> 0, ทำ
    • cst :=เปิดรายการที่เล็กที่สุดจากฮีป
    • cur :=เปิดรายการที่เล็กที่สุดจากฮีป
    • c[cur] :=ขั้นต่ำของ (cst, c[cur])
    • ถ้า (cst, cur) มีอยู่ใน v แล้ว
      • ติดตามตอนต่อไป
    • ถ้า cur เหมือนกับ e แล้ว
      • ส่งคืน c[cur]
    • เพิ่มคู่ (cst, cur) ให้กับ v
    • สำหรับเพื่อนบ้านแต่ละคน n_cost ใน G[cur], do
      • ดันค่า ((n_cost OR cst) เพื่อนบ้าน) ไปที่ฮีป
  • ส่งคืน c[e]
• G :=[รายการใหม่ที่มี n + 1 รายการอิโมติคอน]
• สำหรับแต่ละรายการในขอบ ทำ
  • u :=item[0]
  • v :=item[1]
  • w :=item[2]
  • ใส่คู่ (v, w) ที่ส่วนท้ายของ G[u]
  • ใส่คู่ (u, w) ที่ส่วนท้ายของ G[v]
• ตอบ :=helper(G, s, e)
• ส่งคืน -1 ถ้า ans เหมือนกับ inf ไม่เช่นนั้นให้ส่งคืน ans

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

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

อินพุต

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

ผลลัพธ์

15