آموزش الگوریتم بلمن فورد Bellman-Ford algorithm — تصویری و گام به گام + کد پایتون

الگوریتم بلمن فورد «Bellman-Ford algorithm» برای حل مسائل کوتاه‌ترین مسیر در گراف‌های وزن‌دار استفاده می‌شود. در این مقاله از آموزش‌های پی‌استور می‌خواهیم به آموزش الگوریتم بلمن فورد بپردازیم.

مقدمه

الگوریتم بلمن فورد یک الگوریتم کارآمد برای حل مسائل کوتاه‌ترین مسیر در گراف‌های وزن‌دار است. این الگوریتم نخستین بار توسط ریچارد بلمن و لروی فورد در سال ۱۹۵۸ معرفی شد. هدف اصلی این الگوریتم، یافتن کوتاه‌ترین مسیر از یک راس مبدأ به تمام راس‌های دیگر در گراف‌های وزن‌دار است.

تعریف الگوریتم بلمن فورد

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

با این حال، این الگوریتم در مواجهه با چرخه‌های منفی عملکرد متفاوتی دارد. اگر پس از اجرای n-1 تکرار، در تکرار nام همچنان مقدار فاصله‌ی حداقل یک رأس تغییر کند، نشان‌دهنده‌ی وجود یک چرخه‌ی منفی در گراف است. این ویژگی، بلمن فورد را به ابزاری مفید برای تشخیص و شناسایی چرخه‌های منفی در داده‌ها تبدیل کرده است.

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

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

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

1. پیدا کردن کوتاه‌ترین مسیرها در گراف‌های با وزن منفی: بلمن فورد قابلیت یافتن کوتاه‌ترین مسیرها در گراف‌هایی که ممکن است یال‌های با وزن منفی داشته باشند را دارد. این ویژگی باعث می‌شود که برای مسائلی که در آن‌ها یال‌های با وزن منفی وجود دارند، الگوریتم بلمن فورد مناسب باشد.
2. تشخیص وجود دورهای منفی: یکی از ویژگی‌های خاص الگوریتم بلمن فورد این است که می‌تواند وجود دورهای منفی در گراف را شناسایی کند. اگر پس از انجام تمام گام‌های الگوریتم، هنوز بتوانیم مسیری با کاهش وزن پیدا کنیم، به این معناست که گراف حاوی دور منفی است.
3. شبکه‌های ارتباطی و مسیریابی: بلمن فورد در شبکه‌های ارتباطی مانند مسیریابی در شبکه‌های کامپیوتری که ممکن است هزینه مسیرها منفی باشد (مثلاً در مدل‌هایی که پاداش یا تخفیف در مسیریابی دارند) کاربرد دارد.
4. برنامه‌ریزی حمل و نقل: در مسائلی که مربوط به برنامه‌ریزی مسیرها در شبکه‌های حمل و نقل هستند، مثل جابجایی کالا و مسافران بین شهرها، بلمن فورد می‌تواند به پیدا کردن بهترین مسیرها (حتی در صورتی که تخفیف‌هایی در مسیرهای خاص وجود داشته باشد) کمک کند.
5. مسائل مالی و اقتصادی: در برخی از مدل‌های اقتصادی که شامل جریان پول و اعتبار هستند، ممکن است تخفیف‌ها یا مشوق‌هایی در سیستم وجود داشته باشد که باعث ایجاد یال‌های با وزن منفی می‌شود. الگوریتم بلمن فورد می‌تواند در تحلیل این مدل‌ها استفاده شود.
6. تحلیل شبکه‌های اجتماعی: در شبکه‌های اجتماعی که گاهی روابط منفی (مثلاً دشمنی یا ارتباطات منفی) نیز ممکن است وجود داشته باشد، بلمن فورد می‌تواند برای تحلیل چنین شبکه‌هایی مورد استفاده قرار گیرد.

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

پاورپوینت الگوریتم بلمن فورد — یافتن کوتاه ترین مسیر

کلیک کنید

مثال برای الگوریتم بلمن فورد

برای اینکه بتوانیم راحت‌تر الگوریتم را توضیح دهیم، گراف زیر را در نظر بگیرید.

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

در الگوریتم بلمن فورد برای آغاز فرآیند، ابتدا تمامی یال‌های خروجی گراف در یک جدول به ترتیب الفبایی ثبت می‌شوند.

پس از آن، مانند الگوریتم دیکسترا، جدولی برای نگهداری اطلاعات مربوط به فاصله‌ی هر رأس از رأس مبدأ و پیشینیان هر رأس ایجاد می‌شود. مقدار فاصله‌ی همه‌ی رأس‌ها، به‌جز رأس مبدأ، در ابتدا بی‌نهایت در نظر گرفته می‌شود، چراکه هنوز هیچ مسیری به آن‌ها مشخص نشده است. در این جدول، متغیر d نمایانگر فاصله‌ی رأس‌ها از مبدأ و متغیر π نشان‌دهنده‌ی پیشینیان هر رأس در مسیر بهینه است.

گام ۲: به‌روزرسانی فاصله‌ها (Relaxation)

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

تکرار اول

در نخستین تکرار، ابتدا یال A-C بررسی می‌شود که هزینه‌ی آن برابر با ۳- است. اما از آنجایی که مقدار فاصله‌ی A در این لحظه بی‌نهایت است، مقدار C نیز بی‌تغییر و همچنان بی‌نهایت باقی می‌ماند. این وضعیت برای یال A-E نیز رخ می‌دهد که هزینه‌ی آن ۲ است. از آنجا که مقدار A هنوز بی‌نهایت است، مقدار E نیز بدون تغییر می‌ماند.

بررسی یال‌های دیگر همچون B-F، C-B، C-H، F-G، G-B و H-D نیز نشان می‌دهد که هیچ‌یک از این مسیرها تأثیری بر مقدار رأس‌های مقصد ندارند، زیرا مقدار اولیه‌ی آن‌ها همچنان بی‌نهایت است. اما زمانی که یال S-A مورد بررسی قرار می‌گیرد، نتیجه‌ی متفاوتی حاصل می‌شود.

این یال دارای وزن ۵ است و از آنجایی که مقدار فاصله‌ی رأس S در ابتدا صفر در نظر گرفته شده، مقدار جدید A برابر با ۵ خواهد شد. در این لحظه، پیشینیان A نیز برابر با S در نظر گرفته می‌شود. به این ترتیب، پس از پایان اولین تکرار، الگوریتم بلمن فورد موفق شده است مسیر کوتاه A را از رأس S بیابد.

تکرار دوم

در تکرار دوم، همه‌ی یال‌ها بار دیگر بررسی می‌شوند. اما تنها مسیرهایی اهمیت دارند که مبدأ آن‌ها رأس‌هایی باشد که فاصله‌ی آن‌ها از مبدأ مشخص شده است. در این مرحله، یال‌های متصل به S و A ارزش بررسی دارند، زیرا مقدار سایر رأس‌ها هنوز بی‌نهایت است.

ابتدا یال A-C بررسی می‌شود که وزن آن برابر با ۳- است. از آنجایی که مقدار A اکنون برابر با ۵ است، مقدار C به ۲ = (۳-) + ۵ تغییر می‌یابد و پیشینیان آن A در نظر گرفته می‌شود. یال A-E نیز با وزن ۲ مقدار E را به ۵ = 2 + ۵ تغییر می‌دهد و پیشینیان آن را A تنظیم می‌کند.

یال C-B نیز قابل به‌روزرسانی است، زیرا مقدار C اکنون مشخص شده است. مقدار جدید B برابر با ۹ = 7 + ۲ می‌شود و پیشینیان آن C خواهد بود. یال C-H نیز مقدار H را به ۱- = (۳-) + ۲ کاهش می‌دهد و آن را تحت تأثیر C قرار می‌دهد.

یالهای F-G و G-B نمی‌توانند به‌روزرسانی شوند. پس در ادامه، یال H-D بررسی شده و مقدار D به ۰ = 1 + (۱-) تغییر می‌کند.

در نهایت، سایر یال‌ها تغییری در مقدار رأس‌های خود ایجاد نمی‌کنند. از آنجا که فاصله‌ی A از یال S-A همچنان برابر با ۵ است، نیازی به به‌روزرسانی نیست. بنابراین، تکرار دوم در الگوریتم بلمن فورد به پایان می‌رسد.

تکرار سوم

در تکرار سوم، الگوریتم تمام یال‌ها را مجدداً بررسی کرده و مسیرهای جدیدی را شناسایی می‌کند. مقدار یال‌های A-C و A-E بدون تغییر باقی می‌ماند، اما یال B-F اکنون می‌تواند مقدار جدیدی را ثبت کند. مقدار جدید F برابر با ۴ = (۵-) + ۹ خواهد شد و پیشینیان آن B در نظر گرفته می‌شود.

در این مرحله، یال F-G نیز تأثیرگذار خواهد بود. مقدار جدید G برابر با ۶ = 2 + ۴ خواهد شد و پیشینیان آن F ثبت می‌شود.

سپس، یال G-B بررسی می‌شود که می‌تواند مقدار B را به ۱۰ = 4 + ۶ تغییر دهد، اما از آنجا که مسیر کوتاه‌تری از طریق C-B وجود دارد، مقدار B تغییر نمی‌کند.

تکرار چهارم

در تکرار چهارم، تمامی یال‌ها یک‌بار دیگر مورد بررسی قرار می‌گیرند. اما مشاهده می‌شود که هیچ تغییری در مقادیر ثبت‌شده رخ نمی‌دهد. این نشان می‌دهد که تمام کوتاه‌ترین مسیرها شناسایی شده‌اند و الگوریتم در این مرحله به پایان می‌رسد.

اگر این گراف دارای یک چرخه‌ی منفی بود، پس از انجام n-1 تکرار (که در آن n تعداد رأس‌ها است)، به‌طور تئوری الگوریتم بلمن فورد باید کوتاه‌ترین مسیرها را به تمام رأس‌ها پیدا می‌کرد. اما در تکرار n-ام، اگر مقدار فاصله‌ی حداقل یک رأس تغییر کند، این نشان‌دهنده‌ی وجود یک چرخه‌ی منفی در گراف است.

گام ۳: بررسی وجود چرخه‌ی منفی

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

تکرار اول

جدولی شامل مقادیر اولیه‌ی فاصله و پیشینیان رأس‌ها ایجاد می‌شود. مقدار فاصله برای تمامی رأس‌ها، به‌جز رأس مبدأ (S)، برابر با بی‌نهایت قرار داده می‌شود.

یال S-A که دارای وزن ۳ است، مقدار A را به ۳ = 3 + ۰ تغییر می‌دهد و پیشینیان آن S قرار داده می‌شود.

در ادامه، یال S-B با وزن ۶ مقدار B را به ۶ = 6 + ۰ تغییر می‌دهد، پیشینیان همچنان S می‌باشد.

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

تکرار دوم

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

در تکرار دوم، یال A-B بررسی شده و مقدار جدید B برابر با ۸ = 5 + ۳ خواهد شد. اما از آنجا که مقدار فعلی آن ۶ است، تغییری ایجاد نمی‌شود. در مقابل، یال B-C مقدار C را به ۸ = 2 + ۶ تغییر می‌دهد.

سپس، یال C-A بررسی می‌شود و مقدار جدید A به ۲- = (۱۰-) + ۸ کاهش می‌یابد، چراکه مسیر جدید کوتاه‌تر از مقدار اولیه‌ی آن است. از آنجا که فاصله‌ی A از طریق یال C-A کمتر از فاصله‌ی A از طریق S-A است، مقدار فاصله‌ی A به‌روزرسانی می‌شود.

تکرار سوم

یال‌های S-A و S-B هیچ بروزرسانی ندارند، بنابراین تکرار دوم کامل می‌شود. سپس، تکرار سوم آغاز می‌شود.

در تکرار سوم، یال A-B بررسی می‌شود. فاصله‌ی فعلی تا A برابر با ۲- است، بنابراین فاصله‌ی جدید تا B از طریق یال A-B محاسبه می‌شود، مقدار B از طریق A-B به ۳ = 5 + (۲-) کاهش می‌یابد.

از آنجا که فاصله‌ی جدید B از طریق A-B کمتر از فاصله‌ی فعلی آن از طریق S-B است، مقدار فاصله‌ی B به ۳ به‌روزرسانی می‌شود. همچنین، پیشینیان رأس B به A تغییر می‌کند.

در ادامه، مقدار C از طریق B-C به ۵ = 2 + ۳ تغییر پیدا می‌کند.

در ادامه، یال C-A مقدار A را به ۵- = (۱۰-) + ۵ کاهش می‌دهد. فاصله‌ی رأس A به ۵- واحد به‌روزرسانی می‌شود.

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

در تکرار بعدی، مقدار B مجدداً کاهش یافته و به ۰ = 5 + (۵-) می‌رسد. در نتیجه، فاصله‌ی B به ۰ به‌روزرسانی می‌شود.

از آنجا که مقدار فاصله در تکرار n-ام تغییر کرده است، این نشان می‌دهد که در تکرار n+1 نیز مقادیر تغییر خواهند کرد و این روند به‌طور نامحدود ادامه می‌یابد. این رفتار نشان‌دهنده‌ی وجود یک چرخه‌ی منفی در گراف است، زیرا مسیر A-B-C-A مقدار منفی ایجاد می‌کند.

۳- = (۱۰-) + ۲ + ۵ نشان می‌دهد که این مسیر دارای چرخه‌ی منفی است. وجود چنین چرخه‌ای باعث می‌شود که مقادیر فاصله‌ها به‌طور نامحدود کاهش یابند، که به معنای آن است که کوتاه‌ترین مسیرها را نمی‌توان به‌طور قطعی تعیین کرد.

پاورپوینت تکنیک های مرتب سازی

کلیک کنید

پیاده سازی الگوریتم بلمن فورد

در این بخش کد پیاده‌سازی الگوریتم بلمن فورد (Bellman-Ford algorithm) برای حل مسائل کوتاه‌ترین مسیر در گراف‌های وزن‌دار، به زبان پایتون آورده شده است.

# Python program to find single source shortest path using
# Bellman-Ford algorithm

def bellmanFord(V, edges, src):
    
    # Initially distance from source to all other vertices 
    # is not known(Infinite).
    dist = [100000000] * V
    dist[src] = 0

    # Relaxation of all the edges V times, not (V - 1) as we
    # need one additional relaxation to detect negative cycle
    for i in range(V):
        for edge in edges:
            u, v, wt = edge
            if dist[u] != 100000000 and dist[u] + wt < dist[v]:
                
                # If this is the Vth relaxation, then there 
                # is a negative cycle
                if i == V - 1:
                    return [-1]
                
                # Update shortest distance to node v
                dist[v] = dist[u] + wt
    return dist

if __name__ == '__main__':
    V = 5
    edges = [[1, 3, 2], [4, 3, -1], [2, 4, 1], [1, 2, 1], [0, 1, 5]]

    src = 0
    ans = bellmanFord(V, edges, src)
    print(' '.join(map(str, ans)))

پیچیدگی زمانی: پیچیدگی زمانی الگوریتم بالا به صورت زیر است:

$$O(V*E)$$

زیرا الگوریتم به تعداد V بار تکرار می‌شود تا تمام رأس‌ها را بررسی کند. همچنین در هر تکرار، تمام یال‌ها (E) بررسی می‌شوند تا فاصله‌ها به‌روزرسانی شوند. در گراف‌های بدون وزن منفی یا غیرجهت‌دار، الگوریتم‌هایی مانند Dijkstra سریع‌تر هستند. در ادامه هر بخش از کد را توضیح می‌دهیم:

۱- تعریف توابع کمکی:

در این کد، تنها یک تابع کمکی به نام bellmanFord تعریف شده است که ورودی‌های زیر را دریافت می‌کند:

• V: تعداد رأس‌های گراف
• edges: لیستی از یال‌های گراف که شامل [مبدأ، مقصد، وزن] هستند
• src: رأس مبدأ که می‌خواهیم کوتاه‌ترین مسیر از آن را محاسبه کنیم

این تابع مقدار کوتاه‌ترین مسیر از src به سایر رأس‌ها را در یک لیست ذخیره کرده و در صورت وجود دور منفی مقدار [-۱] را برمی‌گرداند.

۲- عملکرد الگوریتم بلمن فورد:

الگوریتم بلمن فورد برای یافتن کوتاه‌ترین مسیر از یک مبدأ در گراف‌های وزن‌دار به کار می‌رود و مراحل زیر را انجام می‌دهد:

1. مقدار فاصله تمام رأس‌ها از مبدأ را بی‌نهایت (عدد خیلی بزرگ) در نظر می‌گیریم، به‌جز مبدأ که مقدار آن ۰ است.
2. برای V بار تمام یال‌ها را بررسی می‌کنیم:
   • اگر مسیر جدیدی که از یک یال عبور می‌کند کوتاه‌تر باشد، مقدار آن را به‌روز می‌کنیم.
3. اگر در آخرین (Vمین) تکرار مقدار یک رأس تغییر کند، یعنی دور منفی وجود دارد و الگوریتم [-۱] را برمی‌گرداند.
4. در غیر این صورت، آرایه‌ای که کوتاه‌ترین مسیرها را ذخیره کرده است، خروجی داده می‌شود.

۳- عملکرد کد:

• ابتدا تعداد رأس‌ها و لیستی از یال‌های گراف (edges) مشخص می‌شود.
• سپس تابع bellmanFord برای محاسبه‌ی کوتاه‌ترین مسیر از رأس ۰ اجرا می‌شود.
• اگر گراف دور منفی نداشته باشد، برنامه آرایه‌ی فاصله‌ی کوتاه‌ترین مسیرها را چاپ می‌کند.
• اگر دور منفی وجود داشته باشد، مقدار [-۱] برگردانده می‌شود.

خروجی:

۰ ۵ ۶ ۶ ۷

نتیجه گیری

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