পাইথনে গ্রাফে ন্যূনতম পেনাল্টি वाले পথ বের করার প্রোগ্রাম

মনে করুন একটি অনডায়রিক্টেড, ওজনযুক্ত গ্রাফ দেওয়া আছে এবং আমাদের নোড a থেকে নোড b-এ যাওয়ার জন্য ন্যূনতম সম্ভাব্য পেনাল্টি वाला পথ বের করতে বলা হয়েছে। একটি পথের পেনাল্টি হলো সেই পথে ব্যবহৃত সকল এজ ওজনের বিটওয়াইজ OR। আমাদের এমন 'ন্যূনতম পেনাল্টি' পথ খুঁজে বের করতে হবে, এবং যদি দুটি নোডের মধ্যএ কোনো পথ না থাকে, তবে -1 রিটার্ন করব।

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

শুরু (s) = 1, শেষ (e) = 3 হলে, আউটপুট হবে ১৫।

ভের্টেক্স ১ এবং ৩-এর মধ্যে দুটি পথ আছে। সর্বোত্তম পথ 1→2→3, পথের খরচ (10 OR 5) = ১৫।

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

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

helper() ফাংশন ডিফাইন করুন। এটি G, s, e প্যারামিটার নেবে
- v := একটি নতুন সেট
- c := n সাইজের একটি লিস্ট infinity দিয়ে ফিল করা
- heap := (0, s) জোড়া ধারণকারী একটি হিপ
- যখন heap-এর সাইজ > 0, तब
  - cst := heap- থেকে সবচেয়ে ছোট আইটেম পপ করুন
  - cur := heap- থেকে সবচেয়ে ছোট আইটেম পপ করুন
  - c[cur] := min(cst, c[cur])
  - যদি (cst, cur) v-এ থাকে, তবে
    - নেক্সট ইটারেশনে যান
  - যদি cur == e হয়, তবে
    - c[cur] রিটার্ন করুন
  - (cst, cur) কে v-এ অ্যাড করুন
  - G[cur]-এ থাকা প্রতিটি neighbor, n_cost-এর জন্য
    - ((n_cost OR cst), neighbor) কে heap-এ পুশ করুন
- 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