न्यूनतम दंड (पायथन) वाले ग्राफ़ में दो शीर्षों के बीच पथ का पता लगाने का कार्यक्रम

मान लीजिए कि हमें एक अप्रत्यक्ष, भारित ग्राफ दिया गया है और नोड ए से नोड बी तक न्यूनतम संभव दंड के साथ पथ का पता लगाने के लिए कहा गया है। पथ का दंड पथ के सभी किनारों के भार का या बिटवाइज़ है। इसलिए, हमें ऐसे 'न्यूनतम दंड' पथ का पता लगाना चाहिए, और यदि दो नोड्स के बीच कोई पथ मौजूद नहीं है, तो हम -1 लौटाते हैं।

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

प्रारंभ (एस) =1, अंत (ई) =3; तो आउटपुट 15 होगा।

शीर्ष 1 और 3 के बीच दो पथ मौजूद हैं। इष्टतम पथ 1->2->3 है, पथ की लागत (10 या 5) =15 है।

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

एक फंक्शन हेल्पर () को परिभाषित करें। इसमें G, s, e
- v :=एक नया सेट
- c :=आकार n की एक नई सूची जिसे अनंत मान के साथ प्रारंभ किया गया है
- ढेर:=जोड़ी युक्त एक नया ढेर (0, s)
- ढेर का आकार> 0, करते समय
  - cst :=हीप से सबसे छोटी वस्तु को पॉप करें
  - cur :=ढेर से सबसे छोटी वस्तु को पॉप करें
  - c[cur] :=न्यूनतम (cst, c[cur])
  - अगर (cst, cur) v में मौजूद है, तो
    - अगले पुनरावृत्ति के लिए जाएं
  - यदि वक्र ई के समान है, तो
    - वापसी c[cur]
  - जोड़ी (cst, cur) को v में जोड़ें
  - प्रत्येक पड़ोसी के लिए, n_कॉस्ट जी में[cur], करें
    - मान ((n_cost OR cst), पड़ोसी) को ढेर करने के लिए पुश करें
- वापसी c[e]
G :=[एक नई सूची जिसमें n + 1 भावनात्मक सूचियां हैं]
किनारों में प्रत्येक आइटम के लिए, करें
- यू:=आइटम [0]
- v:=आइटम[1]
- w:=आइटम[2]
- G[u] के अंत में जोड़ी (v, w) डालें
- G[v] के अंत में जोड़ी (u, w) डालें
उत्तर:=सहायक(जी, एस, ई)
वापसी -1 यदि उत्तर inf के समान है अन्यथा उत्तर लौटाएं

उदाहरण

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

गणित आयात infdef सहायक (जी, एस, ई) से

import heapq
from math import inf

def helper(G, s, e):
    v = set()
    c = [inf] * len(G)
    heap = [(0, s)]
    while len(heap) > 0:
        cst, cur = heapq.heappop(heap)
        c[cur] = min(cst, c[cur])
        if (cst, cur) in v:
            continue
        if cur == e:
            return c[cur]
        v.add((cst, cur))
        for neighbor, n_cost in G[cur]:
            heapq.heappush(heap, (n_cost | cst, neighbor))
    return c[e]

def solve(n, edges, s, e):
    G = [[] for _ in range(n + 1)]
    for item in edges:
        u, v, w = map(int, item)
        G[u].append((v, w))
        G[v].append((u, w))
    ans = helper(G, s, e)
    return -1 if ans == inf else ans

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

इनपुट

4, [(1, 2, 10), (2, 3, 5), (2, 4, 15), (1, 4, 20)], 1, 3