পাইথনে একটি নেটওয়ার্কে বার্তা পৌঁছাতে কতক্ষণ সময় লাগবে তা খুঁজে বের করার প্রোগ্রাম

ধরুন আমাদের একটি সংখ্যা এবং প্রান্তের একটি তালিকা আছে। এই n বিভিন্ন নোডগুলি 0 থেকে N হিসাবে লেবেলযুক্ত। এই নোডগুলি একটি নেটওয়ার্ক গঠন করছে। প্রতিটি প্রান্ত একটি অনির্দেশিত গ্রাফের (a, b, t) আকারে রয়েছে, এটি প্রতিনিধিত্ব করছে যদি আমরা a থেকে b বা b থেকে a তে বার্তা পাঠাতে চেষ্টা করি তবে এটিতে সময় লাগবে। যখন একটি নোড একটি বার্তা পায়, এটি অবিলম্বে একটি প্রতিবেশী নোডে বার্তা বন্যা. সমস্ত নোড সংযুক্ত থাকলে, নোড 0 থেকে শুরু হওয়া একটি বার্তা পেতে প্রতিটি নোডের জন্য কতক্ষণ সময় লাগবে তা আমাদের খুঁজে বের করতে হবে৷

সুতরাং, যদি ইনপুটটি n =3 প্রান্ত =[[0, 1, 3], [1, 2, 4], [2, 3, 2]] এর মত হয়, তাহলে আউটপুট হবে 9, 4র্থ নোড হিসাবে ( নোড নম্বর 3) 0 -> 1 -> 2 -> 3 থেকে বার্তা গ্রহণ করে যা 3 + 4 + 2 =9 পরিমাণ সময় নেয়৷

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

একটি ফাংশন build_graph() সংজ্ঞায়িত করুন। এটি প্রান্ত লাগবে

• গ্রাফ :=একটি খালি মানচিত্র
• প্রত্যেকটির জন্য (src, dest, t) প্রান্তে সেট করুন, করুন
  • গ্রাফে (dest, t) সন্নিবেশ করান[src]
  • গ্রাফে (src, t) সন্নিবেশ করান [dest]
• রিটার্ন গ্রাফ
• প্রধান পদ্ধতি থেকে নিম্নলিখিতগুলি করুন -
• গ্রাফ :=বিল্ড_গ্রাফ(এজ)
• পরিদর্শন করেছেন :=একটি নতুন সেট
• heap :=জোড়া দিয়ে একটি নতুন গাদা তৈরি করুন (0, 0)
• যখন স্তূপ খালি না হয়, কর
  • (current_total_time, node) :=স্তূপের শীর্ষ উপাদান, এবং স্তূপ থেকে মুছে ফেলুন
  • নোডকে পরিদর্শন করা হিসাবে চিহ্নিত করুন
  • যদি পরিদর্শন করা নোডের সংখ্যা (n + 1) এর মতো হয়, তাহলে
    • বর্তমান_মোট_সময় ফেরত দিন
  • গ্রাফ[নোড]-এ প্রতিটি জোড়ার (nei, সময়) জন্য, করুন
    • যদি না দেখেন, তাহলে
      • ঢোকান জোড়া (বর্তমান_মোট_সময় + সময়, 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