মডিউল ৭_১ঃ কেন দরকার Bellmanford?

আমরা সিঙ্গেল সোর্স শর্টেস্ট পাথ এলগোরিদম এর মধ্যে bfs ও dijkstra দেখেছি। যদি একটি unweighted গ্রাফ থাকে তাহলে bfs এর মাধ্যমে শর্টেস্ট পাথ বের করতে শিখেছি। আর যদি weighted গ্রাফ থাকে তাহলে dijkstra ব্যবহার করে শর্টেস্ট পাথ বের করতে শিখেছি। লাইফ সর্ট তাই না। বাট এবার যদি বলি গ্রাফ এ নেগেটিভ সাইকেল বিদ্যমান।

ধরুন এখানে সোর্স ০ এবং সেটা থেকে আপনি Dijkstra ট্রাভারসাল শুরু করেছেন। তাহলে প্রতিবার ট্রাভারসাল এর পর নোড গুলো রিল্যাক্স হতে থাকবে কেননা ০->১ এ যাওয়ার সময় তার কস্ট হবে -৩। ০->১->২ এ যাওয়ার সময় তার কস্ট হবে ০।০->১->২->০ এ আসতে কস্ট হবে -৫। তাহলে যেই ০ এর মান distance array তে আগে ০ ছিলো সেটা এখন হবে -৫। তাই সে আবার ট্রাভারসাল করা শুরু করবে এবং প্রতিবার ট্রাভারসাল করে সে কমতেই থাকবে। তাই এখানে Dijkstra ইনফাইনাইট লুপ এ পড়ে যাবে। তাই গ্রাফে যদি নেগেটিভ সাইকেল থাকে তাহলে Bellman ford algorithm ব্যবহার করব। Bellman form algorithm নেগেটিভ সাইকেল কে ডিটেক্ট করে ট্রাভারসাল বন্ধ করে দেয়।