पायथन में भारित ग्राफ से संभावित न्यूनतम लागत का पता लगाने का कार्यक्रम

मान लीजिए कि हमारे पास पूर्णांकों की एक 2D सूची है जिसे किनारों कहा जाता है जो एक अप्रत्यक्ष ग्राफ का प्रतिनिधित्व करते हैं। इनपुट में प्रत्येक पंक्ति एक किनारे का प्रतिनिधित्व करती है [यू, वी, डब्ल्यू] जिसका अर्थ है कि नोड्स यू और वी जुड़े हुए हैं और किनारे का वजन डब्ल्यू है। ग्राफ़ में 0 से n-1 तक n नोड्स होते हैं।

पथ की लागत को यहां किनारों की संख्या और पथ में किसी भी किनारे के लिए अधिकतम वजन के गुणनफल के रूप में परिभाषित किया गया है। हमें नोड 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]

  • ग्राफ़ के अंत में आपको डालें[v]

  • वज़न [यू, वी] :=डब्ल्यू

  • वज़न [v, u] :=w

  • N :=अधिकतम N, u + 1, v + 1

  • max_weight :=मैक्सिमम मैक्स_वेट, w

• परिणाम:=अनंत

• जबकि max_weight>=0, करें

  • घ, वजन:=bfs(0, max_weight)

  • यदि d>=0, तो

    • परिणाम :=न्यूनतम परिणाम, d * वजन

    • max_weight :=weight - 1

  • अन्यथा,

    • लूप को समाप्त करें

• परिणाम अगर परिणाम <अनंतता अन्यथा -1

• फ़ंक्शन को परिभाषित करें bfs() । यह जड़ लेगा, weight_cap

  • लक्ष्य:=एन - 1

  • Q :=जड़ युक्त एक डेक, 0, 0

  • दौरा किया :=[झूठा] * एन

  • विज़िट किया गया[0] :=सच

  • जबकि Q खाली नहीं है, करें

    • v, d, current_weight :=Q से अंतिम तत्व हटाएं

    • यदि v, N-1 के समान है, तो

      • वापसी d, current_weight

    • ग्राफ़ में प्रत्येक w के लिए[v], करें

      • अगर विज़िट किया गया [w] शून्य नहीं है, तो

        • अगला पुनरावृत्ति जारी रखें

      • new_weight :=weights[v, w]

      • अगर new_weight <=weight_cap, तो

        • विज़िट किया गया[w] :=सच

        • Q के बाईं ओर (w, d + 1, अधिकतम (current_weight, new_weight)) जोड़ें

  • वापसी -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