الگوریتم Bellman-Ford

نویسنده : آیسان بهرمند
ارسال شده در: 11 ژوئن 2025
ارسال دیدگاه: 0

سلام به همه‌ی دوستانی که عاشق دنیای الگوریتم‌ها و برنامه‌نویسی هستن! امروز قراره با هم یه سفر هیجان‌انگیز به دنیای الگوریتم بلمن-فورد داشته باشیم. این الگوریتم یکی از ابزارهای قدرتمند تو جعبه‌ابزار برنامه‌نویس‌هاست که برای پیدا کردن کوتاه‌ترین مسیر تو یه گراف وزن‌دار استفاده می‌شه. حالا اگه این حرفا براتون یه کم گنگه، نگران نباشید! قراره با زبون خودمونی و ساده، این الگوریتم رو از صفر تا صد توضیح بدم، طوری که انگار داریم دور یه میز قهوه می‌خوریم و گپ می‌زنیم. این پست برای کسایی نوشته شده که می‌خوان یه مطلب کامل و جامع برای وبلاگشون داشته باشن، پس تا آخر همراه من باشید که قراره کلی چیز یاد بگیریم!

الگوریتم Bellman-Ford چیه؟

بیایم اول ببینیم این الگوریتم Bellman-Ford اصلاً به چه دردی می‌خوره. فرض کنید یه نقشه دارید که چندتا شهر روشه و بین این شهرها جاده‌هایی با فاصله‌های مختلف وجود داره. حالا می‌خواید از یه شهر (مثلاً تهران) به یه شهر دیگه (مثلاً شیراز) برید و کوتاه‌ترین مسیر رو پیدا کنید. اگه جاده‌ها فقط فاصله‌های مثبت داشته باشن، الگوریتم‌هایی مثل دیکسترا می‌تونن به‌سرعت این کار رو براتون انجام بدن. اما اگه تو مسیر یه سری جاده‌ها هزینه‌ی منفی داشته باشن چی؟ مثلاً فرض کنید یه جاده به جای اینکه هزینه‌ای ازتون بگیره، بهتون پول بده که ازش رد بشید (مثل تخفیف یا یارانه)! اینجاست که الگوریتم بلمن-فورد وارد بازی می‌شه.

الگوریتم بلمن-فورد یه روشه برای پیدا کردن کوتاه‌ترین مسیر از یه نقطه‌ی شروع (گره مبدا) به همه‌ی گره‌های دیگه تو یه گراف وزن‌دار. نکته‌ی مهمش اینه که برخلاف دیکسترا، می‌تونه با وزن‌های منفی هم کار کنه. البته یه شرط داره: تو گراف نباید چرخه‌ی منفی وجود داشته باشه (چرخه‌ای که مجموع وزن‌هاش منفی باشه)، وگرنه الگوریتم بهمون هشدار می‌ده که همچین چیزی وجود داره و نمی‌تونه کوتاه‌ترین مسیر رو پیدا کنه.

یه کم تاریخچه: بلمن و فورد کی‌ان؟

این الگوریتم Bellman-Ford به اسم دو نفر نام‌گذاری شده: ریچارد بلمن و لستر فورد. ریچارد بلمن یه ریاضیدان و دانشمند کامپیوتر بود که تو دهه‌ی ۱۹۵۰ روی مسائل بهینه‌سازی و برنامه‌ریزی پویا کار می‌کرد. لستر فورد هم یه ریاضیدان دیگه بود که به همراه بلمن ایده‌های اولیه‌ی این الگوریتم رو مطرح کرد. این دو نفر تو سال‌های ۱۹۵۶ و ۱۹۵۸ مقاله‌هایی منتشر کردن که پایه و اساس این الگوریتم رو شکل داد. حالا که یه کم با تاریخچه آشنا شدیم، بیایم بریم سراغ اصل مطلب!

گراف چیه و چرا مهمه؟

قبل از اینکه بریم سراغ خود الگوریتم، باید یه کم در مورد گراف صحبت کنیم، چون بلمن-فورد روی گراف‌ها کار می‌کنه. گراف یه ساختار داده‌ست که از یه سری گره (یا رأس) و یال (یا لبه) تشکیل شده. گره‌ها مثل همون شهرهای نقشه‌مون هستن و یال‌ها مثل جاده‌هایی که این شهرها رو به هم وصل می‌کنن. هر یال می‌تونه یه وزن داشته باشه که می‌تونه مثبت، منفی یا حتی صفر باشه.

گراف‌ها دو نوعن:

گراف جهت‌دار (Directed Graph): یال‌ها جهت دارن، یعنی مثلاً از تهران به شیراز می‌تونید برید، ولی برعکسش نه.
گراف بدون جهت (Undirected Graph): یال‌ها دوطرفه‌ان، یعنی از تهران به شیراز و از شیراز به تهران می‌تونید برید.

الگوریتم Bellman-Ford روی هر دو نوع گراف کار می‌کنه، ولی معمولاً تو گراف‌های جهت‌دار بیشتر استفاده می‌شه.

حالا بلمن-فورد چطور کار می‌کنه؟

بیایم خودمون رو جای الگوریتم Bellman-Ford بذاریم و ببینیم چطور فکر می‌کنه. فرض کنید یه گراف داریم با چندتا گره و یال. ما یه گره مبدا انتخاب می‌کنیم (مثلاً گره A) و می‌خوایم فاصله‌ی کوتاه‌ترین مسیر از A به همه‌ی گره‌های دیگه رو پیدا کنیم. الگوریتم بلمن-فورد این کار رو تو چند مرحله انجام می‌ده:

مقداردهی اولیه:
- فاصله‌ی گره مبدا به خودش رو صفر می‌ذاریم (چون از A به A هیچ فاصله‌ای نیست!).
- فاصله‌ی بقیه‌ی گره‌ها رو بی‌نهایت در نظر می‌گیریم (چون هنوز نمی‌دونیم چطور بهشون برسیم).
- یه آرایه هم درست می‌کنیم که ذخیره کنه هر گره از کدوم گره‌ی قبلی اومده (این برای بازسازی مسیرها بهمون کمک می‌کنه).
تکرار روی یال‌ها:
- الگوریتم به تعداد |V|-1 بار (که |V| تعداد گره‌هاست) همه‌ی یال‌های گراف رو بررسی می‌کنه.
- برای هر یال (u, v) با وزن w، چک می‌کنه که اگه از گره u به v بریم، فاصله‌ی کوتاه‌تری به v می‌رسیم یا نه. اگه فاصله‌ی جدید کمتر بود، فاصله‌ی v رو آپدیت می‌کنه.
چک کردن چرخه‌ی منفی:
- بعد از |V|-1 بار تکرار، یه بار دیگه همه‌ی یال‌ها رو بررسی می‌کنیم. اگه بازم تونستیم فاصله‌ی کوتاه‌تری پیدا کنیم، یعنی یه چرخه‌ی منفی تو گراف وجود داره و الگوریتم بهمون هشدار می‌ده.

یه مثال ساده

بیایم یه مثال بزنیم که بهتر بفهمیم. فرض کنید یه گراف با ۴ گره داریم: A، B، C و D. یال‌ها این‌جورین:

A به B با وزن ۴
A به C با وزن ۲
B به C با وزن ۳
B به D با وزن ۵
C به D با وزن ۱

حالا می‌خوایم از A به همه‌ی گره‌ها کوتاه‌ترین مسیر رو پیدا کنیم.

قدم اول: مقداردهی اولیه

فاصله‌ی A به خودش = ۰
فاصله‌ی A به B، C و D = بی‌نهایت
آرایه‌ی قبلی (predecessor) خالیه.

قدم دوم: تکرار روی یال‌ها

دور اول:

یال A->B (وزن ۴): فاصله‌ی B می‌شه ۴ (چون ۰ + ۴ = ۴).
یال A->C (وزن ۲): فاصله‌ی C می‌شه ۲.
یال B->C (وزن ۳): فاصله‌ی C از طریق B می‌شه ۴+۳=۷، که از ۲ بیشتره، پس عوضش نمی‌کنیم.
یال B->D (وزن ۵): فاصله‌ی D می‌شه ۴+۵=۹.
یال C->D (وزن ۱): فاصله‌ی D می‌شه ۲+۱=۳، که از ۹ کمتره، پس آپدیت می‌شه.

دور دوم:

دوباره یال‌ها رو بررسی می‌کنیم. این‌بار فاصله‌ها تغییر نمی‌کنن، چون به بهینه‌ترین حالت رسیدن.

قدم سوم: چک کردن چرخه‌ی منفی

یه بار دیگه یال‌ها رو چک می‌کنیم. هیچ فاصله‌ای آپدیت نمی‌شه، پس چرخه‌ی منفی نداریم.

نتیجه:

فاصله‌ی A به A = ۰
فاصله‌ی A به B = ۴
فاصله‌ی A به C = ۲
فاصله‌ی A به D = ۳
مسیرها: A->B، A->C، A->C->D

کد الگوریتم Bellman-Ford

حالا که منطق الگوریتم Bellman-Ford رو فهمیدیم، بیایم یه پیاده‌سازی ساده به زبان پایتون بنویسیم:

class Graph: def __init__(self, vertices): self.V = vertices # تعداد گره‌ها self.graph = [] # لیست یال‌ها

def add_edge(self, u, v, w):
    self.graph.append([u, v, w])

def bellman_ford(self, src):
    # مقداردهی اولیه
    dist = [float("Inf")] * self.V
    dist[src] = 0
    predecessor = [None] * self.V

    # |V|-1 بار تکرار
    for _ in range(self.V - 1):
        for u, v, w in self.graph:
            if dist[u] != float("Inf") and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                predecessor[v] = u

    # چک کردن چرخه‌ی منفی
    for u, v, w in self.graph:
        if dist[u] != float("Inf") and dist[u] + w < dist[v]:
            print("گراف چرخه‌ی منفی داره!")
            return None, None

    return dist, predecessor

پیچیدگی زمانی و مکانی

پیچیدگی زمانی: الگوریتم Bellman-Ford تو بدترین حالت O(V * E) زمان می‌بره، که V تعداد گره‌ها و E تعداد یال‌هاست. این به این دلیله که برای |V|-1 بار، همه‌ی یال‌ها رو بررسی می‌کنیم.
پیچیدگی مکانی: O(V) برای ذخیره‌ی فاصله‌ها و گره‌های قبلی.

مقایسه با دیکسترا:

دیکسترا معمولاً سریع‌تره (O((V + E) log V) با هیپ)، ولی نمی‌تونه وزن‌های منفی رو هندل کنه.
بلمن-فورد کندتره، ولی انعطاف‌پذیرتره چون با وزن‌های منفی کار می‌کنه.

کاربردهای بلمن-فورد

۱. پیدا کردن کوتاه‌ترین مسیر در گراف‌های وزن‌دار با وزن منفی

مهم‌ترین کاربرد الگوریتم Bellman-Ford پیدا کردن کوتاه‌ترین مسیر از یه گره مبدا به بقیه گره‌ها تو یه گراف وزن‌دار جهت‌داره. چیزی که این الگوریتم رو خاص می‌کنه، توانایی کار با وزن‌های منفی روی یال‌هاست. مثلاً:

تو شبکه‌های حمل‌ونقل، ممکنه یه مسیر هزینه‌ی منفی داشته باشه، مثل وقتی که یه شرکت حمل‌ونقل به خاطر تبلیغات یا تخفیف، هزینه‌ی کمتری از شما بگیره.
تو شبکه‌های ارتباطی، مثل اینترنت یا شبکه‌های مخابراتی، بعضی مسیرها ممکنه به دلیل بهینه‌سازی یا سیاست‌های خاص، هزینه‌ی منفی داشته باشن (مثلاً پهنای باند رایگان یا یارانه‌دار).

بلمن-فورد تو این موقعیت‌ها می‌تونه کوتاه‌ترین مسیر رو پیدا کنه، در حالی که الگوریتم‌های مثل دیکسترا تو گراف‌های با وزن منفی به مشکل می‌خورن.

۲. تشخیص چرخه‌های منفی

یکی از ویژگی‌های باحال الگوریتم Bellman-Ford اینه که می‌تونه چرخه‌های منفی تو گراف رو تشخیص بده. چرخه‌ی منفی یه مسیر بسته‌ست که مجموع وزن یال‌هاش منفی می‌شه. این ویژگی تو جاهای زیادی کاربرد داره:

بازارهای مالی و آربیتراژ: فرض کنید گره‌ها ارزهای مختلف (مثل دلار، یورو، بیت‌کوین) و یال‌ها نرخ تبدیل بینشون باشن. اگه یه چرخه‌ی منفی وجود داشته باشه، یعنی می‌تونید با تبدیل پیاپی ارزها سود کنید (آربیتراژ). بلمن-فورد می‌تونه این چرخه‌ها رو پیدا کنه و به تحلیل‌گرهای مالی کمک کنه تا فرصت‌های سودآور رو شناسایی کنن.
تحلیل سیستم‌های اقتصادی: تو مدل‌های اقتصادی که هزینه‌ها و درآمدها به‌صورت گراف مدل می‌شن، تشخیص چرخه‌های منفی می‌تونه نشون‌دهنده‌ی ناپایداری یا مشکلات ساختاری باشه.

۳. بهینه‌سازی شبکه‌های ارتباطی

تو شبکه‌های کامپیوتری و مخابراتی، الگوریتم Bellman-Ford به‌عنوان یه الگوریتم مسیریابی استفاده می‌شه. مثلاً:

پروتکل‌های مسیریابی مثل RIP (Routing Information Protocol): تو شبکه‌های قدیمی‌تر، از نسخه‌های اولیه‌ی بلمن-فورد برای پیدا کردن مسیرهای بهینه بین روترها استفاده می‌شد. گرچه حالا پروتکل‌های پیشرفته‌تری مثل OSPF وجود دارن، ولی بلمن-فورد هنوز تو بعضی سیستم‌های خاص کاربرد داره.
شبکه‌های بی‌سیم یا ad-hoc: تو شبکه‌هایی که گره‌ها مدام جابه‌جا می‌شن (مثل شبکه‌های حسگر یا شبکه‌های موبایلی)، وزن یال‌ها ممکنه تغییر کنه و حتی منفی بشه. بلمن-فورد می‌تونه تو این موقعیت‌ها مسیرهای بهینه رو پیدا کنه.

۴. الگوریتم‌های پیشرفته‌تر (مثل الگوریتم جانسون)

الگوریتم Bellman-Ford یه پایه‌ی مهم برای الگوریتم‌های پیچیده‌تره. مثلاً تو الگوریتم جانسون که برای پیدا کردن کوتاه‌ترین مسیر بین همه‌ی جفت گره‌ها تو گراف‌های با وزن منفی استفاده می‌شه، بلمن-فورد نقش کلیدی داره:

جانسون از بلمن-فورد برای تنظیم وزن‌های گراف استفاده می‌کنه تا وزن‌های منفی حذف بشن، بعد از الگوریتم دیکسترا برای پیدا کردن مسیرها استفاده می‌کنه.
این کاربرد تو مسائل بزرگ مثل تحلیل شبکه‌های اجتماعی یا سیستم‌های لجستیک خیلی مهمه.

۵. مدل‌سازی و حل مسائل بهینه‌سازی

بلمن-فورد تو مسائل بهینه‌سازی که به‌صورت گراف مدل می‌شن هم کاربرد داره:

مدیریت پروژه: تو تکنیک‌هایی مثل CPM (Critical Path Method)، اگه بخوایم هزینه‌ها یا زمان‌های منفی (مثل صرفه‌جویی‌ها) رو مدل کنیم، بلمن-فورد می‌تونه مسیرهای بهینه رو پیدا کنه.
برنامه‌ریزی تولید: تو زنجیره‌های تأمین، ممکنه بعضی فرآیندها هزینه‌ی منفی داشته باشن (مثلاً به خاطر بازیافت یا یارانه). بلمن-فورد می‌تونه بهینه‌ترین مسیر تولید رو مشخص کنه.

۶. تحلیل گراف‌های اجتماعی

تو شبکه‌های اجتماعی، گره‌ها می‌تونن افراد و یال‌ها روابط بینشون باشن. اگه بخوایم تأثیرات مثبت یا منفی (مثلاً اعتماد یا بی‌اعتمادی) رو مدل کنیم، بلمن-فورد می‌تونه مسیرهای بهینه‌ی تعامل یا تأثیرگذاری رو پیدا کنه. مثلاً:

پیدا کردن کوتاه‌ترین مسیر برای انتقال یه پیام تو شبکه‌ای که بعضی روابط هزینه‌ی منفی دارن (مثلاً روابطی که باعث کاهش اعتبار می‌شن).

۷. استفاده در بازی‌ها و شبیه‌سازی‌ها

تو طراحی بازی‌های ویدیویی یا شبیه‌سازی‌ها، گراف‌ها برای مدل‌سازی نقشه‌ها یا مسیرهای حرکت استفاده می‌شن. اگه تو بازی وزن‌های منفی وجود داشته باشه (مثلاً پاداش برای انتخاب یه مسیر خاص)، بلمن-فورد می‌تونه مسیرهای بهینه رو برای کاراکترها یا هوش مصنوعی بازی پیدا کنه.

۸. تشخیص ناهنجاری‌ها در سیستم‌ها

چون بلمن-فورد می‌تونه چرخه‌های منفی رو شناسایی کنه، تو سیستم‌های نظارتی و امنیتی هم کاربرد داره:

تشخیص تقلب: تو سیستم‌های مالی یا تراکنش‌ها، چرخه‌های منفی می‌تونن نشون‌دهنده‌ی فعالیت‌های مشکوک مثل پول‌شویی باشن.
تحلیل سیستم‌های کنترلی: تو مهندسی سیستم‌ها، چرخه‌های منفی می‌تونن نشون‌دهنده‌ی ناپایداری یا خطا باشن.

محدودیت‌ها و نکات

اگه گراف چرخه‌ی منفی داشته باشه، الگوریتم نمی‌تونه کوتاه‌ترین مسیر رو پیدا کنه و فقط هشدار می‌ده.
نسبت به دیکسترا کندتره، پس اگه وزن‌های منفی ندارید، بهتره از دیکسترا استفاده کنید.
برای گراف‌های خیلی بزرگ با تعداد یال‌های زیاد، ممکنه بهینه نباشه.

مقایسه با الگوریتم‌های دیگه

قراره بلمن-فورد رو با الگوریتم‌های دیکسترا، فلوید-وارشال، A* و جانسون مقایسه کنیم. هدفمون اینه که بفهمیم کی و کجا باید از بلمن-فورد استفاده کنیم و کی بهتره سراغ یه الگوریتم دیگه بریم. آماده‌اید؟ بزن بریم!

۱. الگوریتم بلمن-فورد در یک نگاه

قبل از مقایسه، یه مرور سریع: بلمن-فورد کوتاه‌ترین مسیر از یه گره مبدا به همه گره‌های دیگه تو یه گراف وزن‌دار (جهت‌دار یا بدون جهت) پیدا می‌کنه. ویژگی بارزش اینه که می‌تونه وزن‌های منفی رو مدیریت کنه و چرخه‌های منفی رو تشخیص بده. پیچیدگی زمانیش O(V * E) هست (V تعداد گره‌ها و E تعداد یال‌ها) و برای گراف‌های با وزن منفی یا تشخیص آربیتراژ تو بازارهای مالی عالیه.

حالا بیایم ببینیم چطور با بقیه الگوریتم‌ها مقایسه می‌شه.

۲. مقایسه با الگوریتم دیکسترا

دیکسترا یکی از معروف‌ترین الگوریتم‌ها برای پیدا کردن کوتاه‌ترین مسیر از یه گره مبدا به بقیه گره‌هاست. بیایم این دو تا رو کنار هم بذاریم:

نقاط قوت دیکسترا:

سرعت: پیچیدگی زمانی دیکسترا با یه هیپ بهینه O((V + E) log V) هست، که معمولاً از O(V * E) بلمن-فورد سریع‌تره، به‌خصوص تو گراف‌های بزرگ.
سادگی پیاده‌سازی برای گراف‌های معمولی: اگه وزن‌های منفی نداشته باشید، دیکسترا کد تمیزتری داره و سریع‌تر اجرا می‌شه.
مناسب برای گراف‌های پراکنده: تو گراف‌هایی که یال‌های کمی دارن، دیکسترا خیلی خوب عمل می‌کنه.

نقاط ضعف دیکسترا:

ناتوانی در مدیریت وزن‌های منفی: اگه گرافتون حتی یه یال با وزن منفی داشته باشه، دیکسترا به مشکل می‌خوره و ممکنه نتیجه‌ی اشتباه بده.
عدم تشخیص چرخه‌های منفی: دیکسترا نمی‌تونه چرخه‌های منفی رو شناسایی کنه، پس برای کاربردهایی مثل تحلیل مالی مناسب نیست.

نقاط قوت بلمن-فورد نسبت به دیکسترا:

مدیریت وزن‌های منفی: بلمن-فورد می‌تونه تو گراف‌هایی با وزن منفی کار کنه، که برای مسائلی مثل شبکه‌های ارتباطی با هزینه‌های منفی یا بازارهای مالی کاربردیه.
تشخیص چرخه‌های منفی: اگه گرافتون چرخه‌ی منفی داشته باشه، بلمن-فورد هشدار می‌ده، که تو کاربردهایی مثل آربیتراژ خیلی مهمه.

نقاط ضعف بلمن-فورد نسبت به دیکسترا:

کندی: به خاطر پیچیدگی O(V * E)، بلمن-فورد تو گراف‌های بزرگ یا متراکم کندتره.
پیچیدگی بیشتر: نیاز به بررسی همه یال‌ها تو هر دور، پیاده‌سازیش رو یه کم پیچیده‌تر می‌کنه.

کی از کدوم استفاده کنیم؟

اگه گرافتون وزن منفی نداره و سرعت مهمه (مثل مسیریابی GPS)، دیکسترا انتخاب بهتریه.
اگه گرافتون وزن منفی داره یا نیاز به تشخیص چرخه‌های منفی دارید (مثل تحلیل مالی)، بلمن-فورد رو انتخاب کنید.

۳. مقایسه با الگوریتم فلوید-وارشال

فلوید-وارشال یه الگوریتم پویاست که کوتاه‌ترین مسیر بین همه جفت گره‌ها تو گراف رو پیدا می‌کنه، نه فقط از یه مبدا.

نقاط قوت فلوید-وارشال:

کوتاه‌ترین مسیر برای همه جفت‌ها: برخلاف بلمن-فورد که فقط از یه گره مبدا کار می‌کنه، فلوید-وارشال ماتریسی از کوتاه‌ترین مسیرها بین همه گره‌ها می‌ده.
مدیریت وزن‌های منفی: مثل بلمن-فورد، می‌تونه وزن‌های منفی رو هندل کنه و چرخه‌های منفی رو تشخیص بده.
سادگی مفهومی: ایده‌ی الگوریتم خیلی ساده‌ست (بررسی همه گره‌های میانی برای هر جفت).

نقاط ضعف فلوید-وارشال:

پیچیدگی زمانی بالا: پیچیدگی زمانی O(V³) هست، که برای گراف‌های بزرگ می‌تونه خیلی کند باشه، حتی کندتر از بلمن-فورد تو گراف‌های پراکنده.
مصرف حافظه: نیاز به یه ماتریس V × V داره، که تو گراف‌های بزرگ حافظه‌ی زیادی می‌خواد (O(V²)).
عدم تمرکز روی مبدا خاص: اگه فقط به مسیرها از یه گره مبدا نیاز دارید، فلوید-وارشال کار اضافی انجام می‌ده.

نقاط قوت بلمن-فورد نسبت به فلوید-وارشال:

سرعت تو گراف‌های پراکنده: تو گراف‌هایی که تعداد یال‌ها کمه (E خیلی کمتر از V²)، بلمن-فورد با O(V * E) سریع‌تره.
مصرف حافظه کمتر: فقط به آرایه‌های فاصله و گره‌های قبلی (O(V)) نیاز داره، نه ماتریس بزرگ.
تمرکز روی مبدا خاص: اگه فقط به مسیرها از یه گره نیاز دارید، بلمن-فورد بهینه‌تره.

نقاط ضعف بلمن-فورد نسبت به فلوید-وارشال:

محدود به مبدا خاص: بلمن-فورد فقط برای یه گره مبدا کار می‌کنه. اگه بخواید برای همه گره‌ها مسیرها رو پیدا کنید، باید V بار اجراش کنید، که می‌شه O(V² * E) و معمولاً از فلوید-وارشال کندتره.
عدم تولید ماتریس کامل: فلوید-وارشال یه نمای کلی از همه مسیرها می‌ده، که برای تحلیل‌های جامع‌تر بهتره.

کی از کدوم استفاده کنیم؟

اگه به کوتاه‌ترین مسیر بین همه جفت گره‌ها نیاز دارید (مثل تحلیل شبکه‌های اجتماعی)، فلوید-وارشال بهتره.
اگه فقط به مسیرها از یه مبدا نیاز دارید و گرافتون وزن منفی داره، بلمن-فورد انتخاب مناسبیه.

۴. مقایسه با الگوریتم A*

A* یه الگوریتم جستجوی هدایت‌شده‌ست که برای پیدا کردن کوتاه‌ترین مسیر از یه گره مبدا به یه گره مقصد خاص استفاده می‌شه، نه همه گره‌ها.

نقاط قوت A*:

سرعت بالا: A* با استفاده از یه تابع هیوریستیک (حدس هوشمندانه درباره فاصله تا مقصد)، می‌تونه خیلی سریع‌تر از بلمن-فورد و حتی دیکسترا باشه، به‌خصوص تو گراف‌های بزرگ مثل نقشه‌های بازی‌های ویدیویی.
تمرکز روی مقصد خاص: اگه فقط به مسیر به یه گره خاص نیاز دارید، A* بهینه‌تره چون گره‌های غیرمرتبط رو بررسی نمی‌کنه.
انعطاف‌پذیری: با تنظیم هیوریستیک، می‌تونید سرعت و دقت رو کنترل کنید.

نقاط ضعف A*:

نیاز به هیوریستیک خوب: عملکرد A* به شدت به کیفیت تابع هیوریستیک بستگی داره. اگه هیوریستیک بد باشه، ممکنه کند بشه یا حتی مسیر بهینه رو پیدا نکنه.
ناتوانی در مدیریت وزن‌های منفی: مثل دیکسترا، A* با وزن‌های منفی مشکل داره.
عدم تشخیص چرخه‌های منفی: A* نمی‌تونه چرخه‌های منفی رو شناسایی کنه.

نقاط قوت بلمن-فورد نسبت به A*:

مدیریت وزن‌های منفی: بلمن-فورد می‌تونه تو گراف‌های با وزن منفی کار کنه، در حالی که A* نمی‌تونه.
کوتاه‌ترین مسیر به همه گره‌ها: بلمن-فورد مسیرها به همه گره‌ها رو پیدا می‌کنه، ولی A* فقط به یه مقصد خاص.
تشخیص چرخه‌های منفی: برای کاربردهایی مثل تحلیل مالی، بلمن-فورد برتری داره.

نقاط ضعف بلمن-فورد نسبت به A*:

کندی: A* معمولاً خیلی سریع‌تره، چون از هیوریستیک برای محدود کردن جستجو استفاده می‌کنه.
عدم تمرکز روی مقصد خاص: اگه فقط به یه گره مقصد نیاز دارید، بلمن-فورد کار اضافی (بررسی همه گره‌ها) انجام می‌ده.

کی از کدوم استفاده کنیم؟

اگه به مسیر به یه مقصد خاص نیاز دارید و گرافتون وزن منفی نداره و هیوریستیک خوبی دارید (مثل بازی‌های ویدیویی یا مسیریابی)، A* بهترینه.
اگه گرافتون وزن منفی داره یا به مسیرها به همه گره‌ها نیاز دارید، بلمن-فورد رو انتخاب کنید.

۵. مقایسه با الگوریتم جانسون

جانسون یه الگوریتم پیشرفته‌ست که کوتاه‌ترین مسیر بین همه جفت گره‌ها تو گراف‌های با وزن منفی (بدون چرخه منفی) پیدا می‌کنه.

نقاط قوت جانسون:

مدیریت وزن‌های منفی برای همه جفت‌ها: جانسون می‌تونه کوتاه‌ترین مسیر بین همه گره‌ها رو تو گراف‌های با وزن منفی پیدا کنه، که ترکیبی از توانایی‌های بلمن-فورد و دیکستراست.
سرعت بهتر تو گراف‌های پراکنده: پیچیدگی زمانی جانسون O(V² log V + V * E) هست، که تو گراف‌های پراکنده از فلوید-وارشال (O(V³)) سریع‌تره.
استفاده از بلمن-فورد: جانسون از بلمن-فورد به‌عنوان یه مرحله برای تنظیم وزن‌ها استفاده می‌کنه، بعد دیکسترا رو برای هر گره اجرا می‌کنه.

نقاط ضعف جانسون:

پیچیدگی پیاده‌سازی: جانسون ترکیبی از بلمن-فورد و دیکستراست، پس پیاده‌سازیش پیچیده‌تره.
نیاز به گراف بدون چرخه منفی: اگه گراف چرخه منفی داشته باشه، جانسون نمی‌تونه کار کنه.
مصرف حافظه: نیاز به تنظیم وزن‌ها و اجرای چندباره دیکسترا، حافظه و پردازش بیشتری می‌خواد.

نقاط قوت بلمن-فورد نسبت به جانسون:

سادگی: بلمن-فورد برای پیدا کردن مسیرها از یه مبدا ساده‌تره و نیازی به مراحل اضافی مثل تنظیم وزن‌ها نداره.
تشخیص چرخه‌های منفی: بلمن-فورد می‌تونه چرخه‌های منفی رو تشخیص بده، ولی جانسون فرض می‌کنه گراف چرخه منفی نداره.
مناسب برای مبدا خاص: اگه فقط به مسیرها از یه گره نیاز دارید، بلمن-فورد مستقیم‌تره.

نقاط ضعف بلمن-فورد نسبت به جانسون:

عدم پشتیبانی از همه جفت‌ها: برای پیدا کردن مسیرها بین همه جفت گره‌ها، باید بلمن-فورد رو V بار اجرا کنید، که O(V² * E) می‌شه و از جانسون کندتره.
سرعت کمتر تو گراف‌های بزرگ: جانسون تو گراف‌های پراکنده به خاطر استفاده از دیکسترا سریع‌تره.

کی از کدوم استفاده کنیم؟

اگه به کوتاه‌ترین مسیر بین همه جفت گره‌ها تو گراف با وزن منفی نیاز دارید و گراف چرخه منفی نداره، جانسون بهترینه.
اگه فقط به مسیرها از یه مبدا نیاز دارید یا باید چرخه‌های منفی رو تشخیص بدید، بلمن-فورد کافی و ساده‌تره.

جدول مقایسه کلی

برای اینکه یه دید کلی داشته باشید، یه جدول مقایسه‌ای درست کردیم:

الگوریتم	پیچیدگی زمانی	وزن منفی	چرخه منفی	هدف اصلی	بهترین کاربرد
بلمن-فورد	O(V * E)	بله	تشخیص	کوتاه‌ترین مسیر از مبدا	گراف با وزن منفی، تشخیص آربیتراژ
دیکسترا	O((V + E) log V)	خیر	خیر	کوتاه‌ترین مسیر از مبدا	مسیریابی GPS، گراف بدون منفی
فلوید-وارشال	O(V³)	بله	تشخیص	کوتاه‌ترین مسیر همه جفت‌ها	تحلیل شبکه‌های اجتماعی
A*	متغیر (بستگی به هیوریستیک)	خیر	خیر	کوتاه‌ترین مسیر به مقصد خاص	بازی‌های ویدیویی، مسیریابی
جانسون	O(V² log V + V * E)	بله	خیر	کوتاه‌ترین مسیر همه جفت‌ها	گراف پراکنده با وزن منفی

پیاده‌سازی پیشرفته‌تر

بیایم یه نسخه‌ی پیشرفته‌تر از کد رو ببینیم که مسیرهای کوتاه‌ترین رو هم چاپ می‌کنه:

class Graph:
def __init__(self, vertices):
self.V = vertices
self.graph = []

def add_edge(self, u, v, w):
self.graph.append([u, v, w])

def print_path(self, predecessor, j):
if predecessor[j] is None:
print(j, end=” “)
return
self.print_path(predecessor, predecessor[j])
print(j, end=” “)

def bellman_ford(self, src):
dist = [float(“Inf”)] * self.V
dist[src] = 0
predecessor = [None] * self.V

for _ in range(self.V – 1):
updated = False
for u, v, w in self.graph:
if dist[u] != float(“Inf”) and dist[u] + w < dist[v]:
dist[v] = dist[u] + w
predecessor[v] = u
updated = True
if not updated:
break

for u, v, w in self.graph:
if dist[u] != float(“Inf”) and dist[u] + w < dist[v]:
print(“گراف چرخه‌ی منفی داره!”)
return None, None

for i in range(self.V):
if dist[i] != float(“Inf”):
print(f”مسیر به گره {i}: “, end=””)
self.print_path(predecessor, i)
print(f”\nفاصله: {dist[i]}”)
else:
print(f”گره {i} غیرقابل دسترسیه”)

return dist, predecessor

# مثال استفاده
g = Graph(4)
g.add_edge(0, 1, 4)
g.add_edge(0, 2, 2)
g.add_edge(1, 2, 3)
g.add_edge(1, 3, 5)
g.add_edge(2, 3, 1)

distances, predecessors = g.bellman_ford(0)

نتیجه‌گیری

الگوریتم بلمن-فورد یه ابزار قدرتمند و انعطاف‌پذیره که تو خیلی از مسائل واقعی به کار می‌ره. گرچه ممکنه به اندازه‌ی دیکسترا سریع نباشه، اما توانایی کار با وزن‌های منفی و تشخیص چرخه‌های منفی اون رو خاص می‌کنه. تو این پست سعی کردیم با زبون خودمونی و با جزئیات کامل، این الگوریتم رو توضیح بدیم و امیدوارم حالا حسابی باهاش آشنا شده باشید. اگه سوالی دارید یا دوست دارید یه مثال دیگه ببینید، تو کامنت‌ها بگید تا باهم گپ بزنیم!

بیشتر بخوانید: “مزایای SvelteJS در توسعه وب“

آیسان بهرمند

بازدید: