โปรแกรมหาเส้นทางค่าใช้จ่ายขั้นต่ำระหว่างจุดยอดค่าต่ำสุดถึงค่าสูงสุดใน Python

สมมติว่าเราได้รับกราฟไม่มีทิศทางมีน้ำหนัก และต้องการหาเส้นทางที่มีค่าใช้จ่ายเดินทางขั้นต่ำจากโหนดหนึ่งไปยังอีกโหนดหนึ่ง ค่าใช้จ่ายในการเดินทางคำนวณดังนี้: สมมติมีเส้นทางจากจุดยอด A ไป C เป็น A→B→C ค่าใช้จ่ายจาก A ไป B คือ 10 และจาก B ไป C คือ 20 ค่าใช้จ่ายจาก A ไป C จะเป็น (ค่าใช้จ่าย A ถึง B) + (ความต่างของค่าใช้จ่าย B ถึง C และค่าใช้จ่ายสะสมถึง B) คือ 10 + (20 - 10) = 20 เราต้องหาค่าใช้จ่ายเดินทางขั้นต่ำจากโหนดแรกถึงโหนดสุดท้าย (โหนดค่าต่ำสุดถึงค่าสูงสุด) ในกราฟที่กำหนด

เช่น ถ้าอินพุตเป็นดังภาพ ผลลัพธ์จะเป็น 15 มีสองเส้นทางระหว่างจุดยอด 1 และ 4 เส้นทางเหมาะสมคือ 1→2→4 ค่าใช้จ่าย 10 + (15 - 10) = 15 มิฉะนั้นจะใช้ 20

วิธีแก้ปัญหา

• adjList := แมปใหม่ที่มีรายการว่าง
• สำหรับแต่ละ item ใน edges:
  • u := item[0], v := item[1], w := item[2]
  • แทรกคู่ (w,v) ลงท้าย adjList[u]
  • แทรกคู่ (w,u) ลงท้าย adjList[v]
• q := heap ใหม่
• v_list := เซตใหม่
• แทรก (0,1) ลงท้าย q
• flag := True
• while q ไม่ว่าง:
  • c := pop องค์ประกอบเล็กที่สุดจาก q
  • ถ้า c[1] อยู่ใน v_list: ข้ามรอบนี้
  • เพิ่ม c[1] ลง v_list
  • ถ้า c[1] เท่ากับ n: flag := False, return c[0]
  • สำหรับแต่ละ u ใน adjList[c[1]]:
    • ถ้า u[1] ไม่อยู่ใน v_list:
      • out := max(u[0], c[0], u[1])
      • push out ลง heap q
• ถ้า flag เป็น True return -1

ตัวอย่าง

from collections import defaultdict
import heapq

def solve(n, edges):
    adjList = defaultdict(list)
    for item in edges:
        u, v, w = map(int, item)
        adjList[u].append((w, v))
        adjList[v].append((w, u))
    q = []
    v_list = set()
    q.append((0, 1))
    flag = True
    while q:
        c = heapq.heappop(q)
        if c[1] in v_list:
            continue
        v_list.add(c[1])
        if c[1] == n:
            flag = False
            return c[0]
        for u in adjList[c[1]]:
            if u[1] not in v_list:
                out = (max(u[0], c[0]), u[1])
                heapq.heappush(q, out)
    if flag:
        return -1

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

อินพุต

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

เอาต์พุต

15