মডিউল ৭_২ঃ Bellmanford Algorithm
Last updated
Last updated
আমরা এখন Bellmanford এলগোরিদম কিভাবে কাজ করে সেটা সম্পর্কে জানব। সেটার জন্য আমরা নিচের গ্রাফটিকে বিবেচনা করি।
Bellmanford এলগোরিদম এর ক্ষেত্রে আমাদের মাথায় রাখতে হবে এই এলগোরিদম এজ লিস্ট ধরে কাজ করে। তার মানে এইটি প্রতিটি এজ এর কাছে যায় এবং তাকে রিল্যাক্স করা পসিবল কিনা চেক করে।
উপরের গ্রাফটির এজ লিস্টটি যদি খেয়াল করি তাহলে বলতে পারিঃ
০->২
১->৩
২->১
০->৩
তাহলে এখন প্রশ্ন আসতে পারে যে কয়বার রিল্যাক্স করব? তার উত্তর হচ্ছে যে Bellmanford এলগোরিদম worst case এ প্রতিবার একটা করে নোড এর শর্টেস্ট ডিস্টেন্স বের করতে পারে। তাহলে যদি N সংখ্যক নোড থাকে তাহলে N-1 বার রিল্যাক্স করলেই বলতে পারি যে সোর্স থেকে সকল নোড এর শর্টেস্ট ডিস্টেন্স পাওয়া সম্ভব।
এবার তাহলে আমরা আমাদের মেইন প্রসেসটা দেখি।যেহেতু এখানেও পাথ রিল্যাক্স করব তাই শুরুতে সকল নোড এর ডিস্টেন্স ইনফিনিটি ধরে নিলাম ও সোর্স এর ডিস্টেন্স ০ ধরে নিলাম।
প্রথমে আমরা ০->২ এজকে সিলেক্ট করি। তাহলে
dis[0]+cost(0,2) = 5<infinite
তাই ২ এর ডিস্টেন্স আপডেট হয়ে হবে ৫।
এবার ১->৩ কে সিলেক্ট করব।
dis[1]+cost(1,3) = infinte+3 > infinite
তাই ১->৩ আপডেট হবে না।
এবার ২->১ এজকে সিলেক্ট করব।
dis[2]+cost(2,1) = 5+2 = 7< infinity
তাই ১ এর ডিস্টেন্স আপডেট হয়ে হবে ৭।
এবার ০->৩ এজকে সিলেক্ট করব।
dis[0]+cost(0,3) = 0+12 = 12< infinity
তাই ৩ এর ডিস্টেন্স আপডেট হয়ে হবে ১২।
এবার আবার আমরা এজ লিস্ট এর শুরু থেকে সেইম প্রসেস শুরু করব।প্রথমে আমরা ০->২ এজকে সিলেক্ট করি। তাহলে
dis[0]+cost(0,2) = 5 = 5
তাই ২ এর ডিস্টেন্স আপডেট হবে না।
এবার ১->৩ কে সিলেক্ট করব।
dis[1]+cost(1,3) = 7+3 = 10<12
তাই ১->৩ ডিস্টেন্স আপডেট হয়ে হবে ১০।
এবার ২->১ এজকে সিলেক্ট করব।
dis[2]+cost(2,1) = 5+2 = 7 = 7
তাই ১ এর ডিস্টেন্স আপডেট হবে না।
এবার ০->৩ এজকে সিলেক্ট করব।
dis[0]+cost(0,3) = 0+12 = 12>i10
তাই ৩ এর ডিস্টেন্স আপডেট হবে না।
এখন যদি খেয়াল করে দেখো আমরা সোর্স নোড থেকে প্রত্যেক নোড এর শর্টেস্ট ডিস্টেন্স পেয়ে গেছি।
তাহলে সোর্স ০ থেকে সব নোড এর শর্টেস্ট ডিসেটেন্সঃ
তবে Bellmanford এলগোরিদমে আমাদের আরো একটি ব্যাপার খেয়াল রাখতে হবে। সেটি বোঝার জন্য আমরা আরেকটি গ্রাফ দেখি।
এখানে সোর্স ০ ধরে যদি এজ লিস্ট ধরে Bellmanford algorithm চালায় তাহলে নোড ২ কখনো রিল্যাক্স হবে না কেননা ০ থেকে ২ এ যাওয়ার ডাইরেক্ট কিংবা আনডাইরেক্ট কোনো রাস্তা নেই। তবে ২->৩ নোড এ infinite-7 <infinte থেকে ছোট হওয়ায় ৩ নোডটি রিল্যাক্স হবে।
কিন্ত এটা হওয়া উচিত নয়। কেননা ০ থেকে ৩ যাওয়ার কোনো রাস্তা নাই তাই এখানে infinite এই থাকা উচিত।
তাই আমরা Bellmanford algorithm করার সময় এটাও খেয়াল রাখবো যে কোনো নোড রিল্যাক্স হতে চাইলে তার প্যারেন্ট নোড ইনফিনিটি কিনা। যদি হয় তাহলে রিল্যাক্স করব না অন্যথায় করব।
