पायथन में सभी पत्र पहुंचाने के लिए न्यूनतम पथ ज्ञात करने का प्रोग्राम

मान लीजिए 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 से शुरू करता है, तो लागत अन्य दो से अधिक होगी।

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

एक फ़ंक्शन depth_search() परिभाषित करें। यह node, p लेगा
- d1 := -infinity
- d2 := -infinity
- adj_list[node] में प्रत्येक जोड़ी x, y के लिए, करें
  - यदि x p के समान नहीं है, तो
    - d1 := d1 और depth_search(x, node) + y का अधिकतम
    - यदि d1 > d2, तो
      - d2 और d1 के मान स्वैप करें
    - ti[node] := ti[node] + ti[x]
    - यदि 0 < ti[x] < k, तो
      - SUM := SUM + y
  - यदि d1 > 0, तो
    - MAX := MAX और d1 + d2 का अधिकतम
  - यदि d2 > 0 और tj[node] शून्येतर है, तो
    - MAX := MAX और d2 का अधिकतम
  - यदि tj[node] शून्येतर है, तो
    - d2 := max(0, d2)
  - d2 वापस करें
k := delv का आकार
adj_list := एक नया मैप
ti := (nodes + 5) आकार की सूची जिसे 0 से प्रारंभ किया गया हो
tj := (nodes + 5) आकार की सूची जिसे 0 से प्रारंभ किया गया हो
delv में प्रत्येक i के लिए, करें
- ti[i] := 1
- tj[i] := 1
roads में प्रत्येक item के लिए, करें
- x := item[0]
- y := item[1]
- c := item[2]
- यदि x adj_list में मौजूद नहीं है, तो
  - adj_list[x] := []
- यदि y adj_list में मौजूद नहीं है, तो
  - adj_list[y] := []
- (y, c) को adj_list[x] के अंत में जोड़ें
- (x, c) को adj_list[y] के अंत में जोड़ें
SUM := 0
MAX := 0
depth_search(1, 1)
SUM * 2 - MAX वापस करें

उदाहरण

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

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)]