একটি অনির্দেশিত ওজনযুক্ত গ্রাফ দেওয়া আছে যেখানে n নোড রয়েছে (নোডগুলো ০ থেকে শুরু করে নম্বর দেওয়া হয়েছে)। এই গ্রাফটি এজ লিস্ট হিসেবে ইনপুট দেওয়া হয়েছে, প্রতিটি এজ e-এর জন্য সেটি পার করার সাফল্যের সম্ভাবনা probability[e] দেওয়া আছে। আরেকটি স্টার্ট এবং এন্ড নোড দেওয়া আছে। আমাদের কাজ হলো স্টার্ট থেকে এন্ড পর্যন্ত যাওয়ার সর্বোচ্চ সাফল্যের সম্ভাবনাবিশিষ্ট পথ খুঁজে বের করা এবং সেই সম্ভাবনা ফেরত দেওয়া। কোনো পথ না থাকলে ০ ফেরত দিতে হবে।
যেমন, ইনপুট যদি নিচের ছবির মতো হয়:
তবে আউটপুট হবে ০.২৪ কারণ নোড ০ থেকে ২ পর্যন্ত দুটি পথ রয়েছে: একটি সরাসরি পথ যার সম্ভাবনা ০.২, আরেকটি নোড ১ होकर যাওয়ার পথ যার সম্ভাবনা ০.৪ × ০.৬ = ০.২৪। এটি সর্বোচ্চ।
সমাধানের ধাপসমূহ
- g := দেওয়া এজ লিস্ট এবং সম্ভাবনা মানকে ওজন হিসেবে ব্যবহার করে গ্রাফ তৈরি করুন।
- q := একটি কিউ ডেটা স্ট্রাকচার।
- (start, 1) কিউতে डालুন।
- visited := একটি ম্যাপ যেটি ভিজিট করা নোডের সর্বোচ্চ সম্ভাবনা সংরক্ষণ করবে।
- যখন কিউ খালি নয়, তখন:
- (node, prob) := কিউয়ের প্রথম আইটেম বের করুন এবং কিউ থেকে মুছে দিন।
- যদি visited[node] > prob হয়, তবে পরবর্তী ইটারেশনের জন্য যান।
- অন্যথায়, visited[node] := prob সেট করুন।
- g[node]-এর প্রতিটি সংলগ্ন নোড adj এবং সংশ্লিষ্ট সম্ভাবনা nextProb এর জন্য:
- যদি visited[adj] < prob × nextProb হয়, তবে (adj, prob × nextProb) কিউর শেষে যোগ করুন।
- visited[end] ফেরত দিন।
উদাহরণ
from collections import defaultdict, deque
def solve(edges, probability, start, end):
g = defaultdict(list)
for i in range(len(edges)):
src, dst = edges[i][0], edges[i][1]
prob = probability[i]
g[src].append((dst, prob))
g[dst].append((src, prob))
q = deque()
q.append((start, 1))
visited = defaultdict(int)
while q:
node, prob = q.popleft()
if visited[node] > prob:
continue
else:
visited[node] = prob
for adj, nextProb in g[node]:
if visited[adj] < prob * nextProb:
q.append((adj, prob * nextProb))
return visited[end]
edges = [[0,1],[1,2],[0,2]]
probability = [0.5,0.5,0.2]
start = 0
end = 2
print(solve(edges, probability, start, end))
ইনপুট
[[0,1],[1,2],[0,2]], [0.5,0.5,0.2], 0, 2
আউটপুট
0.25
