मान लीजिए हमारे पास एक संख्या n और एज की एक लिस्ट है। ये n अलग-अलग नोड्स हैं जो 0 से N तक लेबल किए गए हैं। ये नोड्स एक नेटवर्क बनाते हैं। प्रत्येक एज (a, b, t) के रूप में एक अनडायरेक्टेड ग्राफ में है, जो दर्शाता है कि यदि हम a से b या b से a संदेश भेजने की कोशिश करते हैं, तो इसमें t समय लगेगा। जब एक नोड संदेश प्राप्त करता है, तो वह तुरंत पड़ोसी नोड पर संदेश फॉरवर्ड करता है। यदि सभी नोड्स जुड़े हुए हैं, तो हमें ढूंढना है कि नोड 0 से शुरू होने वाले संदेश को हर नोड तक पहुंचने में कितना समय लगेगा।
उदाहरण के लिए, यदि इनपुट n = 3, edges = [[0, 1, 3], [1, 2, 4], [2, 3, 2]] है, तो आउटपुट 9 होगा, क्योंकि चौथा नोड (नोड नंबर 3) 0 -> 1 -> 2 -> 3 से संदेश प्राप्त करता है जिसमें 3 + 4 + 2 = 9 समय लगता है।
समाधान दृष्टिकोण
इस समस्या को हल करने के लिए हम डिज्क्स्ट्रा एल्गोरिदम (मिन-हीप के साथ) का उपयोग करेंगे:
- build_graph(edges) फंक्शन परिभाषित करें:
- graph := एक खाली मैप
- प्रत्येक (src, dest, t) के लिए edges में:
- (dest, t) को graph[src] में डालें
- (src, t) को graph[dest] में डालें
- graph लौटाएं
- मुख्य मेथड में:
- graph := build_graph(edges)
- visited := एक नया सेट
- heap := (0, 0) पेयर के साथ नया हीप
- जब तक heap खाली नहीं है:
- (current_total_time, node) := heap का शीर्ष तत्व, heap से हटाएं
- node को visited मार्क करें
- यदि visited नोड्स की संख्या == (n + 1) है, तो current_total_time लौटाएं
- प्रत्येक (nei, time) पेयर के लिए graph[node] में:
- यदि nei visited नहीं है, तो (current_total_time + time, nei) को heap में डालें
पायथन कार्यान्वयन
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