ইউভিএ সমস্যা ১১২৮০

এটা একটি শর্টেস্ট পাথ প্রবলেম। সর্বোচ্চ X টি নোড ব্যবহার করে ১ থেকে N তম নোডে যাবার শর্টেস্ট পাথ বের করতে হবে। সমস্যাটি কয়েকভাবে সমাধান করা যায়। একটি সমাধান হলো dijkstra ব্যবহার করা,এবং কারেন্ট নোডে কয়টি এজ ব্যবহার করে এসেছি তার হিসাব রাখা। সর্বোচ্চ Xটি নোড ব্যবহার করা যাবে এ কথাটিকে অন্যভাবে বলা যায় সর্বোচ্চ X+1 টি এজ ব্যবহার করা যাবে।

আরেকটা সমাধান হলো bellman ford। বেলম্যান ফোর্ডের মূল অ্যালগোরিদম এরকম:

বাইরে লুপটি ১বার শেষ হবার পর আমরা পাবো ১টি এজ ব্যবহার করে শর্টেস্ট পাথ,M বার শেষ হবার পর পাবো সর্বোচ্চ Mটি এজ ব্যবহার করে শর্টেস্ট পাথ। তবে এখানে এজ কোন অর্ডারে নিব সেটি গুরুত্বপূর্ণ। কাছের নোডগুলো আগে আপডেট করলে প্রথম ইটারেশনেই ২য় নোড দিয়ে পরেরগুলো আপডেট হয়ে যেতে পারে। তাই আপডেট করার সময় উল্টা করে করে করতে হবে,সোর্স থেকে দূরের এজগুলোকে আগে নিতে হবে।
আমার কোডটি এরকম:

বেলম্যান ফোর্ড নিয়ে একটা চমতকার টিউটোরিয়াল: http://apps.topcoder.com/forums/?module=Thread&threadID=671406&start=0

Print Friendly, PDF & Email

ফেসবুকে মন্তব্য

comments

Powered by Facebook Comments

4,462 times read (exlcuding bots)

One thought on “ইউভিএ সমস্যা ১১২৮০

Leave a Reply

Your email address will not be published. Required fields are marked *