पायथन में सभी अक्षरों को वितरित करने के लिए न्यूनतम पथ खोजने का कार्यक्रम

मान लीजिए कि n शहर हैं और जो n -1 सड़कों से जुड़े हैं। किसी दूसरे शहर से किसी शहर का भ्रमण किया जा सकता है। अब शहरों की डाक व्यवस्था प्रतिदिन k पत्र वितरित करती है। पत्र का गंतव्य k विभिन्न शहरों में से कोई भी हो सकता है। एक डाक कर्मचारी को हर दिन सभी पत्रों को अपने पते पर पहुंचाना होता है। हमें यह पता लगाना होगा कि सभी पत्रों को वितरित करने के लिए कार्यकर्ता को न्यूनतम दूरी तय करनी होगी। कार्यकर्ता किसी भी शहर से शुरू कर सकता है।

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

और पत्रों को शहरों में पहुंचाना होगा (delv) 1, 2, और 4; तो आउटपुट 4 होगा।

कार्यकर्ता 1, 2, या 4 शहरों से डिलीवरी शुरू कर सकता है। यदि कार्यकर्ता शहर 1 से शुरू करता है, तो पथ 1->2->4 होगा, इसके विपरीत शहर 4 के मामले में; 4->2->1। कुल लागत 1 + 3 =4 होगी। यदि वह शहर 2 से शुरू करता है, तो लागत अन्य दो से अधिक होगी।

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

• एक फ़ंक्शन को परिभाषित करें गहराई_खोज() । यह नोड लेगा, p
  • d1 :=-इन्फिनिटी
  • d2 :=-इन्फिनिटी
  • प्रत्येक जोड़ी के लिए x, y adj_list[node] में, करते हैं
    • यदि x, p के समान नहीं है, तो
      • d1 :=अधिकतम (d1, गहराई_खोज (x, नोड) + y)
      • यदि d1> d2, तो
        • d2 और d1 के मानों की अदला-बदली करें
      • ती[नोड] :=ती[नोड] + ती[x]
      • अगर 0 <ती[x]
      • योग :=योग + y
  • यदि d1> 0, तो
    • MAX :=अधिकतम (MAX, d1 + d2)
  • यदि d2> 0 और tj[नोड] शून्य नहीं है, तो
    • MAX :=अधिकतम (MAX, d2)
  • यदि tj[नोड] शून्य नहीं है, तो
    • d2 :=अधिकतम(0, d2)
  • d2 वापसी

उदाहरण

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

import sys
from math import inf as INF
sys.setrecursionlimit(10**5 + 5)

def depth_search(node, p):
    global SUM, MAX
    d1 = -INF
    d2 = -INF

    for x, y in adj_list[node]:
        if x != p:
            d1 = max(d1, depth_search(x, node) + y)
            if d1 > d2:
                d1, d2 = d2, d1

            ti[node] += ti[x]
            if 0 < ti[x] < k:
                SUM += y

    if d1 > 0: MAX = max(MAX, d1 + d2)
    if d2 > 0 and tj[node]: MAX = max(MAX, d2)
    if tj[node]: d2 = max(0, d2)

    return d2

def solve(nodes, delv, roads):
    global k, ti, tj, adj_list, SUM, MAX
    k = len(delv)
    adj_list = {}
    ti = [0] * (nodes + 5)
    tj = [0] * (nodes + 5)

    for i in delv:
        ti[i] = tj[i] = 1

    for item in roads:
        x, y, c = map(int, item)
        if x not in adj_list: adj_list[x] = []
        if y not in adj_list: adj_list[y] = []

        adj_list[x].append([y, c])
        adj_list[y].append([x, c])

    SUM = 0
    MAX = 0
    depth_search(1,1)
    return SUM * 2 - MAX

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

इनपुट

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

आउटपुट

4