(۰۲ آبان ۱۳۹۱ ۱۲:۲۴ ق.ظ)esi نوشته شده توسط:  توضیحات من طبق کتاب clrs هست چون من فقط الگویتم رو از رویه این کتاب خوندم .
در الگوریتم بلمن فورد، از یک راس مبدا شروع کرده و با تکنیک relaxing جلو رفته و در هر بار مسیره بهینه را انتخاب می کند. ابتدا از راس مبدا شروع کرده و سپس به ازای هر لبه ها آرام سازی رو انجام میده تا کوتاهترین مسیر بین هر u,v انتخاب شود.
در مثال که شما آوردید، مثلا از راس A شروع می کنیم، ابتدا یال ۲و یال ۵ انتخاب میشه که هر دو از گره مبدا شروع می شوند، سپس کوتاه ترین مسیر ممکنه از گره های انتخاب تا کنون با در نظر گرفتن گره واسط محاسبه میشه، پس یال ۳ هم انتخاب میشه، در مرحله بعد الگوریتم سعی در انتخاب یال ۵ داره اما بسته به انتخاب گره بعداز s در پیمایش dfs (چون اگر در هنگام dfs مقادیر اولین لحظه ملاقات یعنی d یا مسیر ABD یا ACD انتخاب میشه ) می تونه یال های ۴و۳(بعد A گره B انتخاب شود)، یا ۲و۳ (بعد A گره C انتخاب شود) و چون وزن جمع آنها یکی است پس بسته به ترتیب پیمایش dfs برای گره d یال ها انتخاب می شن که چون هر دو ۷ هست فرقی نداره اما از لحاظ الگوریتمی گفتم تا بدونید که کدوم مسیر محاسبه برای پیدا کرده گره D استفاده میشه .
روش Relaxing به این صورت هست که پس تعیین مقادیر d و pi (پی یونانی) در پیمایش عمقی ، مشخص می کنه که آیا با داشتن وزن یال بین u,v آیا می توان میسر را بهبود بخشید یا نه ، یعنی آیا اگه u رو به مسیر اضافه کنیم مقداری که تا کنون برای v پیدا شده ببهبود پیدا می کنه (کمتر میشه یا نه) یا نه ؟ اگه شد پس u رو نیز در مسیر قرار بده.