न्यूनतम मूल्य शीर्ष से उच्चतम मूल्य शीर्ष (पायथन) के बीच न्यूनतम लागत पथ का पता लगाने का कार्यक्रम

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

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

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

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

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

• adjList :=खाली सूचियों वाला एक नया नक्शा
• किनारों में प्रत्येक आइटम के लिए, करें
  • यू:=आइटम [0]
  • v:=आइटम[1]
  • w:=आइटम[2]
  • adjList[u]
  . के अंत में जोड़ी (w,v) डालें
  • adjList[v]
  . के अंत में जोड़ी (w,u) डालें
• q :=एक नया ढेर
• v_list :=एक नया सेट
• q के अंत में (0,1) डालें
• झंडा :=सच
• जबकि q खाली नहीं है, करें
  • c :=q से सबसे छोटा आइटम पॉप करें
  • अगर c[1] v_list में मौजूद है, तो
    • अगले पुनरावृत्ति के लिए जाएं
  • v_list में जोड़ें(c[1])
  • यदि c[1] n के समान है, तो
    • झंडा :=झूठा
    • वापसी सी[0]
  • adjList[c[1]] में प्रत्येक आप के लिए,
    . करें
    • यदि आप [1] v_सूची में मौजूद नहीं हैं, तो
      • बाहर :=अधिकतम (u[0], c[0] ,u[1])
      • ढेर क्यू में धकेलें
• अगर झंडा सही है तो
  • वापसी -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)]

आउटपुट

15