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

n নোড (০ থেকে N) এবং এজ লিস্ট edges দেওয়া আছে, প্রতিটি এজ: (a, b, t) (আনডিরেক্টেড, সময় t)। নোড ০ থেকে মেসেজ শুরুর পর সব নোডে মেসেজ পৌঁছাতে কত সময় লাগবে (সর্বোচ্চ শর্টেস্ট পাথ) বের করতে হবে।

উদাহরণস্বরূপ, n=3, edges=[[0,1,3],[1,2,4],[2,3,2]] হলে আউটপুট ৯ (পথ: ০→১→২→৩, সময় ৩+৪+২=৯)।

সমাধানের পদ্ধতি (ডায়েকস্ট্রা অ্যালগরিদম / প্রায়োরিটি কিউ)

অ্যাডজেসেন্সি লিস্ট graph বানান।
visited সেট, heap = [(0, 0)] (time, node)।
হিপ খালি না হওয়া পর্যন্ত:
- (curr_time, node) = heappop(heap)।
- যদি ভিজিটেড হয়, স্কিপ করুন।
- ভিজিটেডে যোগ করুন।
- যদি len(visited) == n+1: curr_time রিটার্ন করুন (সব নোড পৌঁছেছে)।
- নেইবরগুলোর জন্য heappush(heap, (curr_time + t, 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)
            if node in visited:
                continue
            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]]