पायथन में शॉर्टकट में दो शहरों के बीच की लंबाई का पता लगाने का कार्यक्रम

मान लीजिए कि n शहरों की संख्या है और शहर दो प्रकार की सड़कों से जुड़े हुए हैं; राजमार्ग और शॉर्टकट। अब, एक नक्शा है और नक्शे पर केवल राजमार्ग मौजूद हैं और सभी शॉर्टकट अनुपस्थित हैं। शहरों का परिवहन विभाग एक ऐसा परिवहन शुरू करना चाहता है जो शहरों को राजमार्गों और शॉर्टकट का उपयोग करके जोड़ता है। हम जानते हैं कि दो शहरों के बीच एक शॉर्टकट है जब उनके बीच कोई राजमार्ग नहीं है। यहां हमारा काम एक प्रारंभिक शहर से अन्य सभी शहरों के लिए शॉर्टकट के रूप में न्यूनतम दूरी का पता लगाना है।

तो, अगर इनपुट पसंद है

और स्टार्ट वर्टेक्स 1 है, तो आउटपुट 3 1 2 होगा।

अगर हम केवल शॉर्टकट लेते हैं, तो शहरों 1 और 2 के बीच का रास्ता 1->3->4->2 होगा और लागत 3 होगी।

इसी तरह,

1 और 3:1->3, लागत 1.

1 और 4:1->3->4, लागत 2.

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

• ग्राफ:=n सेट वाली एक नई सूची
• किनारों में प्रत्येक जोड़ी (x, y) के लिए, करें
  • x :=x - 1
  • y :=y - 1
  • y को ग्राफ़ में डालें[x]
  • ग्राफ़ में x डालें[y]
• temp_arr :=आकार n की एक नई सरणी जिसमें मान -1 है
• b_set :=एक नया नक्शा जिसमें कुंजी s - 1 है
• f :=एक नया सेट जिसमें 0 से n और b_set के बीच का अंतर है
• सूचकांक:=0
• जबकि b_set का आकार> 0, करें
  • b_set में प्रत्येक तत्व a के लिए करें
    • temp_arr[a] :=अनुक्रमणिका
  • nxt :=एक नया मानचित्र जिसमें ग्राफ़ के मान शामिल हैं जो b_set के उपसमुच्चय नहीं हैं
  • f :=f और nxt का अंतर सेट करें
  • b_set :=nxt
  • सूचकांक :=अनुक्रमणिका + 1
• temp_arr के गैर-शून्य मान लौटाएं

उदाहरण

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

def solve(n, edges, s):
    graph = [set() for i in range(n)]
    for (x, y) in edges:
        x -= 1
        y -= 1
        graph[x].add(y)
        graph[y].add(x)
    temp_arr = [-1] * n
    b_set = {s - 1}
    f = set(range(n)).difference(b_set)
    index = 0
    while len(b_set) > 0:
        for a in b_set:
            temp_arr[a] = index
        nxt = {f for f in f if not b_set.issubset(graph[f])}
        f = f.difference(nxt)
        b_set = nxt
        index += 1
    return (' '.join(str(t) for t in temp_arr if t > 0))    

print(solve(4, [(1, 2), (2, 3), (1, 4)], 1))

इनपुट

4, [(1, 2), (2, 3), (1, 4)], 1

आउटपुट

3 1 2