पायथन में दो शीर्षों के बीच न्यूनतम पेनल्टी वाला पथ ज्ञात करने का प्रोग्राम

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

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

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

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

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

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

उदाहरण

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

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