โปรแกรมค้นหาต้นทุนขั้นต่ำที่เป็นไปได้จากกราฟถ่วงน้ำหนักใน Python

สมมติว่าเรามีรายการ 2 มิติของจำนวนเต็มที่เรียกว่า edge ซึ่งเป็นตัวแทนของกราฟที่ไม่มีทิศทาง ทุกแถวในอินพุตแสดงถึงขอบ [u, v, w] หมายถึงโหนด u และ v เชื่อมต่อกัน และขอบมีน้ำหนัก w กราฟประกอบด้วย n โหนดตั้งแต่ 0 ถึง n-1

ต้นทุนของเส้นทางถูกกำหนดไว้ที่นี่เป็นผลคูณของจำนวนขอบและน้ำหนักสูงสุดสำหรับขอบใดๆ ในเส้นทาง เราต้องหาต้นทุนขั้นต่ำที่เป็นไปได้จากโหนด 0 ถึงโหนด n-1 หรือประกาศคำตอบเป็น -1 หากไม่มีเส้นทางดังกล่าว

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

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

• กราฟ :=แผนที่ใหม่

• น้ำหนัก :=แผนที่ใหม่

• max_weight :=0

• ไม่มี :=0

• สำหรับแต่ละ u, v, w ในขอบ ทำ

  • แทรก v ที่ส่วนท้ายของกราฟ[u]

  • ใส่ u ที่ท้ายกราฟ[v]

  • น้ำหนัก[u, v] :=w

  • น้ำหนัก[v, u] :=w

  • N :=สูงสุดของ N, u + 1, v + 1

  • max_weight :=สูงสุดของ max_weight w

• ผลลัพธ์ :=อนันต์

• ในขณะที่ max_weight>=0 ทำ

  • d, น้ำหนัก :=bfs(0, max_weight)

  • ถ้า d>=0 แล้ว

    • ผลลัพธ์ :=ผลลัพธ์ขั้นต่ำ d * น้ำหนัก

    • max_weight :=น้ำหนัก - 1

  • มิฉะนั้น

    • ยุติการวนซ้ำ

• ส่งคืนผลลัพธ์หากผลลัพธ์ <อินฟินิตี้เป็นอย่างอื่น -1

• กำหนดฟังก์ชัน bfs() สิ่งนี้จะหยั่งราก weight_cap

  • เป้าหมาย :=N - 1

  • Q :=deque ที่มีรูท, 0, 0

  • เข้าชมแล้ว :=[เท็จ] * N

  • เข้าชมแล้ว[0] :=จริง

  • ในขณะที่ Q ไม่ว่างเปล่าให้ทำ

    • v, d, current_weight :=ลบองค์ประกอบสุดท้ายออกจาก Q

    • ถ้า v เหมือนกับ N - 1 แล้ว

      • ส่งคืน d, current_weight

    • สำหรับแต่ละ w ในกราฟ[v] ทำ

      • ถ้า visit[w] ไม่เป็นศูนย์ แล้ว

        • ดำเนินการซ้ำต่อไป

      • new_weight :=น้ำหนัก[v, w]

      • ถ้า new_weight <=weight_cap แล้ว

        • เยี่ยมชม[w] :=จริง

        • เพิ่ม (w, d + 1, สูงสุด (current_weight, new_weight)) ที่ด้านซ้ายของ Q

  • กลับ -1, -1

ตัวอย่าง

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

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

อินพุต

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

ผลลัพธ์

600