โปรแกรมค้นหาเส้นทางต้นทุนขั้นต่ำระหว่างจุดยอดค่าต่ำสุดไปยังจุดยอดมูลค่าสูงสุด (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 :=แผนที่ใหม่ที่มีรายการว่าง
• สำหรับแต่ละรายการในขอบ ทำ
  • u :=item[0]
  • v :=item[1]
  • w :=item[2]
  • ใส่คู่ (w,v) ที่ส่วนท้ายของ adjList[u]
  • ใส่คู่ (w,u) ที่ส่วนท้ายของ adjList[v]
• q :=กองใหม่
• v_list :=ชุดใหม่
• แทรก (0,1) ที่ส่วนท้ายของ q
• flag :=จริง
• ในขณะที่ q ไม่ว่างเปล่า ให้ทำ
  • c :=ป๊อปรายการที่เล็กที่สุดจาก q
  • ถ้า c[1] มีอยู่ใน v_list แล้ว
    • ติดตามตอนต่อไป
  • เพิ่ม(c[1]) ลงใน v_list
  • ถ้า c[1] เหมือนกับ n แล้ว
    • ธง :=เท็จ
    • ส่งคืน c[0]
  • สำหรับแต่ละ u ใน adjList[c[1]] ทำ
    • ถ้า u[1] ไม่มีอยู่ใน v_list แล้ว
      • ออก :=สูงสุดของ (u[0], c[0] ,u[1])
      • ดันออกไปในกอง q
• ถ้าแฟล็กเป็น True แล้ว
  • คืน -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