> For the complete documentation index, see [llms.txt](https://phitron.gitbook.io/algorithm/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://phitron.gitbook.io/algorithm/bellmanford-floyd-warshall/_-bellmanford-algorithm.md). # মডিউল ৭\_২ঃ Bellmanford Algorithm আমরা এখন Bellmanford এলগোরিদম কিভাবে কাজ করে সেটা সম্পর্কে জানব। সেটার জন্য আমরা নিচের গ্রাফটিকে বিবেচনা করি।

Bellmanford এলগোরিদম এর ক্ষেত্রে আমাদের মাথায় রাখতে হবে এই এলগোরিদম এজ লিস্ট ধরে কাজ করে। তার মানে এইটি প্রতিটি এজ এর কাছে যায় এবং তাকে রিল্যাক্স করা পসিবল কিনা চেক করে। উপরের গ্রাফটির এজ লিস্টটি যদি খেয়াল করি তাহলে বলতে পারিঃ ০->২ ১->৩ ২->১ ০->৩ তাহলে এখন প্রশ্ন আসতে পারে যে কয়বার রিল্যাক্স করব? তার উত্তর হচ্ছে যে Bellmanford এলগোরিদম worst case এ প্রতিবার একটা করে নোড এর শর্টেস্ট ডিস্টেন্স বের করতে পারে। তাহলে যদি N সংখ্যক নোড থাকে তাহলে N-1 বার রিল্যাক্স করলেই বলতে পারি যে সোর্স থেকে সকল নোড এর শর্টেস্ট ডিস্টেন্স পাওয়া সম্ভব। এবার তাহলে আমরা আমাদের মেইন প্রসেসটা দেখি।যেহেতু এখানেও পাথ রিল্যাক্স করব তাই শুরুতে সকল নোড এর ডিস্টেন্স ইনফিনিটি ধরে নিলাম ও সোর্স এর ডিস্টেন্স ০ ধরে নিলাম।

**বি দ্রঃ এখানে নীল রং দিয়ে Distance আর কমলা রঙ দিয়ে কস্ট বোঝানো হচ্ছে।**

প্রথমে আমরা ০->২ এজকে সিলেক্ট করি। তাহলে dis\[0]+cost(0,2) = 5\

বি দ্রঃ এখানে নীল রং দিয়ে Distance আর কমলা রঙ দিয়ে কস্ট বোঝানো হচ্ছে।

এবার ১->৩ কে সিলেক্ট করব। 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 \

কিন্ত এটা হওয়া উচিত নয়। কেননা ০ থেকে ৩ যাওয়ার কোনো রাস্তা নাই তাই এখানে infinite এই থাকা উচিত। **তাই আমরা Bellmanford algorithm করার সময় এটাও খেয়াল রাখবো যে কোনো নোড রিল্যাক্স হতে চাইলে তার প্যারেন্ট নোড ইনফিনিটি কিনা। যদি হয় তাহলে রিল্যাক্স করব না অন্যথায় করব।**