पायथन में न्यूनतम मान वाले शीर्ष से अधिकतम मान वाले शीर्ष तक न्यूनतम लागत पथ ज्ञात करने का प्रोग्राम

मान लीजिए हमें एक अनिर्देशित, भारित ग्राफ दिया गया है और हमें एक विशेष नोड से दूसरे विशेष नोड तक न्यूनतम संभव यात्रा लागत वाला पथ ढूंढना है। यात्रा लागत की गणना निम्न प्रकार से की जाती है: मान लीजिए शीर्ष A से शीर्ष C तक A→B→C जैसा पथ है। A से B तक यात्रा की लागत 10 है और B से C तक यात्रा की लागत 20 है। A से C तक यात्रा की लागत (A से B तक यात्रा की लागत) + (B से C तक यात्रा की लागत और नोड B तक संचयी यात्रा लागत का अंतर) होगी। तो यह 10 + (20 - 10) = 20 होगा। हमें दिए गए ग्राफ में पहले नोड से अंतिम नोड (सबसे कम मान वाले नोड से सबसे अधिक मान वाले नोड) तक न्यूनतम संभव यात्रा मान ज्ञात करने हैं।

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

तो आउटपुट 15 होगा।

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

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

adjList := खाली सूचियों वाला एक नया मैप
edges में प्रत्येक item के लिए, करें
- u := item[0]
- v := item[1]
- w := item[2]
- जोड़ी (w,v) को adjList[u] के अंत में डालें
- जोड़ी (w,u) को adjList[v] के अंत में डालें
q := एक नया हीप
v_list := एक नया सेट
(0,1) को q के अंत में डालें
flag := True
जब तक q खाली नहीं है, करें
- c := q से सबसे छोटा आइटम निकालें
- यदि c[1] v_list में मौजूद है, तो
  - अगली पुनरावृत्ति के लिए जाएं
- c[1] को v_list में जोड़ें
- यदि c[1] n के समान है, तो
  - flag := False
  - c[0] वापस करें
- adjList[c[1]] में प्रत्येक u के लिए, करें
  - यदि u[1] v_list में मौजूद नहीं है, तो
    - out := u[0], c[0], u[1] का अधिकतम
    - out को हीप q में डालें
यदि flag True है तो
- -1 वापस करें

उदाहरण

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

from collections import defaultdict
import heapq

def solve(n, edges):
    adjList = defaultdict(list)
    for item in edges:
        u, v, w = map(int, item)
        adjList[u].append((w, v))
        adjList[v].append((w, u))
    q = []
    v_list = set()
    q.append((0, 1))
    flag = True
    while q:
        c = heapq.heappop(q)
        if c[1] in v_list:
            continue
        v_list.add(c[1])
        if c[1] == n:
            flag = False
            return c[0]
        for u in adjList[c[1]]:
            if u[1] not in v_list:
                out = (max(u[0], c[0]), u[1])
                heapq.heappush(q, out)
    if flag:
        return -1

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

इनपुट

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