पायथन में नेटवर्क में संदेशों तक पहुंचने में कितना समय लगेगा, यह जानने के लिए कार्यक्रम

मान लीजिए कि हमारे पास एक संख्या और किनारों की एक सूची है। ये n अलग-अलग नोड्स 0 से N के रूप में लेबल किए गए हैं। ये नोड्स एक नेटवर्क बना रहे हैं। प्रत्येक किनारा एक अप्रत्यक्ष ग्राफ के रूप (ए, बी, टी) में है, यह दर्शाता है कि अगर हम ए से बी या बी से ए को संदेश भेजने का प्रयास करते हैं, तो इसमें टी समय लगेगा। जब कोई नोड संदेश प्राप्त करता है, तो यह तुरंत संदेश को पड़ोसी नोड पर बाढ़ कर देता है। यदि सभी नोड्स जुड़े हुए हैं, तो हमें यह पता लगाना होगा कि प्रत्येक नोड को नोड 0 से शुरू होने वाले संदेश को प्राप्त करने में कितना समय लगेगा।

इसलिए, यदि इनपुट n =3 किनारों =[[0, 1, 3], [1, 2, 4], [2, 3, 2]] जैसा है, तो आउटपुट 9 होगा, जैसा कि चौथा नोड ( नोड संख्या 3) 0 -> 1 -> 2 -> 3 से संदेश प्राप्त करता है जिसमें 3 + 4 + 2 =9 राशि समय लगता है।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

एक फ़ंक्शन को परिभाषित करें build_graph() । इसमें किनारे लगेंगे

• ग्राफ:=एक खाली नक्शा
• किनारों में सेट प्रत्येक (src, dest, t) के लिए, करें
  • ग्राफ़ में (dest, t) डालें[src]
  • ग्राफ़ में (src, t) डालें[dest]
• रिटर्न ग्राफ़
• मुख्य विधि से निम्न कार्य करें -
• ग्राफ:=build_graph(किनारों)
• विज़िट किया :=एक नया सेट
• ढेर:=जोड़ी के साथ एक नया ढेर बनाएं (0, 0)
• जबकि ढेर खाली नहीं है, करें
  • (current_total_time, node) :=हीप का शीर्ष तत्व, और इसे हीप से हटा दें
  • नोड को विज़िट किया गया के रूप में चिह्नित करें
  • यदि विज़िट किए गए नोड्स की संख्या (n + 1) के समान है, तो
    • वर्तमान_कुल_समय लौटाएं
  • ग्राफ में प्रत्येक जोड़ी (एनईआई, समय) के लिए[नोड], करते हैं
    • अगर नी का दौरा नहीं किया, तो
      • जोड़ी (current_total_time + time, nei) को ढेर में डालें

उदाहरण (पायथन)

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

import heapq
from collections import defaultdict
class Solution:
   def solve(self, n, edges):
      graph = self.build_graph(edges)  
      visited = set()
      heap = [(0, 0)]
      while heap:
         current_total_time, node = heapq.heappop(heap)
         visited.add(node)  
         if len(visited) == (n + 1):
            return current_total_time
         for nei, time in graph[node]:
            if nei not in visited:
               heapq.heappush(heap, (current_total_time + time, nei))
   def build_graph(self, edges):
      graph = defaultdict(set)
      for src, dest, t in edges:
         graph[src].add((dest, t))
         graph[dest].add((src, t))
      return graph
ob = Solution()
n = 3
edges = [[0, 1, 3],[1, 2, 4],[2, 3, 2]]
print(ob.solve(n, edges))

इनपुट

3, [[0, 1, 3],[1, 2, 4],[2, 3, 2]]

इनपुट

9