पायथन में शॉर्टकट्स के माध्यम से दो शहरों के बीच की दूरी ज्ञात करने का प्रोग्राम

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

इसलिए, यदि इनपुट इस तरह है

और प्रारंभिक शीर्ष (s) 1 है, तो आउटपुट 3 1 2 होगा।

यदि हम केवल शॉर्टकट लेते हैं, तो शहर 1 और 2 के बीच का मार्ग 1→3→4→2 होगा, और लागत 3 होगी।

इसी तरह,

1 और 3: 1→3, लागत 1।

1 और 4: 1→3→4, लागत 2।

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

• graph := n सेट वाली एक नई सूची
• edges में प्रत्येक जोड़ी (x, y) के लिए, करें
  • x := x - 1
  • y := y - 1
  • y को graph[x] में डालें
  • x को graph[y] में डालें
• temp_arr := -1 मान वाली आकार n की एक नई सरणी
• b_set := कुंजी s - 1 वाला एक नया मैप
• f := 0 से n तक की संख्याओं और b_set के बीच का अंतर वाला एक नया सेट
• index := 0
• जब तक b_set का आकार > 0, करें
  • b_set में प्रत्येक तत्व a के लिए, करें
    • temp_arr[a] := index
  • nxt := एक नया मैप जिसमें graph के वे मान हों जो b_set का उपसमुच्चय न हों
  • f := f और nxt का अंतर
  • b_set := nxt
  • index := index + 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