Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> Python

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


मान लीजिए हमारे पास एक संख्या 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
  1. Python में कितने क्यूब कटे हैं, यह खोजने का प्रोग्राम Python में कितने क्यूब कटे हैं, यह खोजने का प्रोग्राम

    मान लीजिए, a, b, और c आयामों के कई क्यूब्स हैं, और उनका उपयोग करके axbxc आयाम का एक नया बॉक्स बनाया जाता है। a, b, और c pairwise को-प्राइम हैं; gcd(a, b) = gcd(b,c) = gcd(c, a) = 1। हमें एक सिंगल स्लाइस के साथ बॉक्स को दो टुकड़ों में काटना है जैसा कि चित्र में दिखाया गया है। हमें यह पता करना है कि य

  1. Python Program कैसे चलाएं? Python Program कैसे चलाएं?

    Code लिखने के बाद, हमें code को execute करके output प्राप्त करने के लिए run करने की आवश्यकता होती है। Program चलाने पर, हम जांच सकते हैं कि लिखा गया code सही है और desired output produce करता है। Python program चलाना काफी आसान काम है। IDLE पर चलाएं IDLE पर python program चलाने के लिए, दिए गए steps क

  1. सभी पेड़ों को जलाने में लगने वाले दिनों की संख्या ज्ञात करने का पायथन प्रोग्राम सभी पेड़ों को जलाने में लगने वाले दिनों की संख्या ज्ञात करने का पायथन प्रोग्राम

    मान लीजिए हमारे पास एक 2D मैट्रिक्स है जो एक जंगल को दर्शाता है जहां तीन प्रकार के सेल हैं: 0 खाली सेल, 1 पेड़ सेल, 2 जलता हुआ पेड़ सेल। हर दिन, एक पेड़ आग पकड़ लेता है जब उसके आसन्न (ऊपर, नीचे, बाएं, दाएं, विकर्ण नहीं) पेड़ में आग लगी हो। हमें वह दिनों की संख्या ढूंढनी है जो हर पेड़ को जलाने में ल