পাইথনে ন্যূনতম মানের ভের্টেক্স থেকে সর্বোচ্চ মানের ভের্টেক্স পর্যন্ত ন্যূনতম খরচের পথ বের করার প্রোগ্রাম

মনে করুন একটি অনডায়ریک্টেড, ওজনযুক্ত গ্রাফ দেওয়া আছে এবং আমাদের একটি নির্দিষ্ট নোড থেকে অন্য নির্দিষ্ট নোডে যাওয়ার জন্য ন্যূনতম সম্ভাব্য যাত্রা খরচ বের করতে বলা হয়েছে। যাত্রার খরচ নিচের পদ্ধতিতে হিসাব করা হয়: ধরুন A থেকে C পর্যন্ত পথ A→B→C। A থেকে B-এর খরচ ১০ এবং B থেকে C-এর খরচ ২০। A থেকে C-এর যাত্রা খরচ হবে (A থেকে B-এর খরচ) + (B থেকে C-এর খরচ - B-এ পৌঁছানোর ক্যুমুলেটিভ খরচ)। অর্থাৎ ১০ + (২০ - ১০) = ২০। আমাদের দেওয়া গ্রাফে সবচেয়ে কম মানवाले নোড থেকে সবচেয়ে বেশি মানवाले নোড পর্যন্ত ন্যূনতম যাত্রা খরচ বের করতে হবে।

যেমন, ইনপুট এমন হলে

আউটপুট হবে ১৫।

ভের্টেক্স ১ এবং ৪-এর মধ্যে দুটি পথ আছে। সর্বোত্তম পথ 1→2→4, খরচ ১০ + (১৫ - ১০) = ১৫। অন্যটা ২০ খরচ করবে।

সমাধান পদ্ধতি

এই সমস্যাটি সমাধান করতে নিচের ধাপগুলো অনুসরণ করুন:

adjList := খালি লিস্ট ধারণকারী একটি ম্যাপ
edges-এ থাকা প্রতিটি item-এর জন্য
- u := item[0], v := item[1], w := item[2]
- (w,v) কে adjList[u]-এ এবং (w,u) কে adjList[v]-এ অ্যাপেন্ড করুন
q := একটি নতুন হিপ (heap)
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 := max(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)]