الگوریتم بلمن-فورد (Bellman-Ford Algorithm)، در ریاضیات (Mathematics)
انواع روش های بهینه سازی (Optimization Methods) را در آموزش زیر شرح دادیم :
الگوریتم بلمن-فورد (Bellman-Ford Algorithm) :
📌 معرفی
الگوریتم بلمن-فورد (Bellman-Ford Algorithm) یک الگوریتم برای یافتن کوتاه ترین مسیر از یک مبدأ به تمام گره های دیگر در گراف هایی است که می توانند وزن های منفی داشته باشند. برخلاف دیکسترا، بلمن-فورد می تواند وجود دورهای منفی (Negative Cycles) را نیز تشخیص دهد. اگر دور منفی وجود داشته باشد، مفهوم کوتاه ترین مسیر تعریف نمی شود.
📐 مراحل الگوریتم
مقادیر فاصله از مبدأ به همه گره ها را بینهایت در نظر بگیر، به جز خود مبدأ که صفر است.
به تعداد
\[ (V-1) \]بار (که V تعداد گره ها است):
برای هر یال
\[ (u, v) \]با وزن w:
اگر
\[ distance[u] + w < distance[v] \]بود،
\[ distance[v] \]را به روز کن.
برای تشخیص دور منفی، یک بار دیگر همه یال ها را بررسی کن. اگر هنوز بتوان فاصله ای را کاهش داد، دور منفی وجود دارد.
🔧 پیچیدگی
پیچیدگی زمانی الگوریتم
\[ O(VE) \]است که برای گراف های متراکم می تواند بالا باشد، اما مزیت آن کار با وزن های منفی است.
