বেলম্যান-ফোর্ড অ্যালগরিদম (Bellman-Ford Algorithm)

ডাইকস্ট্রা (Dijkstra) অ্যালগরিদম অনেক ফাস্ট, কিন্তু তার একটাই কড়া নিয়ম আছে: কোনো রাস্তার দূরত্ব বা খরচ নেগেটিভ বা মাইনাস হতে পারবে না। কিন্তু বাস্তব দুনিয়ার কিছু সমস্যা এই নিয়ম মানে না — যেমন কারেন্সির এক্সচেঞ্জ রেট দিয়ে লাভ বা আর্বিট্রেজ (arbitrage) বের করা, নেটওয়ার্কের খরচের মডেল, অথবা এমন কোনো ম্যাপ যেখানে কোনো বিশেষ রাস্তায় গেলে উল্টো আপনার লাভ বা সেভিংস হয়। ঠিক এই জায়গাগুলোতেই বেলম্যান-ফোর্ড (Bellman-Ford) অ্যালগরিদম কাজে আসে।

বেলম্যান-ফোর্ড শুরুর পয়েন্ট থেকে অন্য সব পয়েন্টে যানয়ার সবচেয়ে ছোট বা সস্তা রাস্তা (Shortest Path) বের করতে পারে, এমনকি রাস্তার খরচ নেগেটিভ হলেও। এর চেয়েও বড় কথা, সে একটা ভয়ংকর পরিস্থিতি ধরে ফেলতে পারে: সেটা হলো নেগেটিভ সাইকেল (Negative cycle) — এমন একটা গোলকধাঁধা বা চক্র যার মোট খরচ মাইনাস। এই চক্রে যতবার ঘুরবেন, আপনার মোট খরচ তত কমতে থাকবে (বা লাভ বাড়তে থাকবে), যার ফলে 'সবচেয়ে ছোট রাস্তা' বলে আর কিছু থাকে না, ফলাফল অসীম বা ইনফিনিটি হয়ে যায়।

অ্যালগরিদমটা কীভাবে কাজ করে?

এর আসল ট্রিকটা হলো: V সংখ্যক শহরের ম্যাপে, একটা শহর দুবার ভিজিট না করে সবচেয়ে লম্বা যে রাস্তাটা বানানো সম্ভব, তাতে সর্বোচ্চ V-1 টা রাস্তা বা এজ (edge) থাকতে পারে (এর বেশি হলেই আপনি আগের দেখা কোনো শহরে আবার চলে আসবেন, মানে সাইকেল তৈরি হবে)। তাই এটার সিম্পল রুল হলো: ম্যাপের সব কটি রাস্তাকে ধরে ধরে ঠিক V-1 বার রিল্যাক্স (relax) বা আপডেট করুন। k বার আপডেট করা হলে, গ্যারান্টি দেওয়া যায় যে সর্বোচ্চ k টা রাস্তা পার হয়ে যত শর্টেস্ট পাথ হওয়া সম্ভব, তার সবগুলোই ক্যালকুলেট করা শেষ।