الگوریتم مسیریابی بلمن فورد (Bellman-Ford)

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

به مثال زیر توجه کنید:

گرافی مطابق شکل داریم، می خواهیم کوتاه ترین فاصله ی راس S تا تمامی نقاط رل به دست آوریم. مطابق الگوی زیر عمل می کنیم:

ابتدا فاصله ی راس S تا نقاط مجاور را محاسبه می کنیم.

سپس از ریوس مجاور حرکت نموده و کوتاه ترین فواصل را بدست می آوریم.

در نهایت به شکل زیر می رسیم.

مطالب مرتبط:

الگوریتم های مسیریابی – بخش اول (الگوریتم دیکسترا) الگوریتم های مسیریابی – بخش دوم (الگوریتم *A) الگوریتم های مسیریابی – بخش چهارم (فلوید وارشال)