موضوع مقاله: الگوریتم بلمن–فورد | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # الگوریتم بلمن–فورد | مقدمه: الگوریتم بلمن-فورد الگوریتم پیمایش گراف است که مسئلهٔ کوتاهترین مسیر از مبدأ واحد را برای گراف‌های وزن‌داری که وزن یال‌ها ممکن است منفی باشد حل می‌کند. | ## بخش 1: الگوریتم بلمن–فورد | الگوریتم دَیکسترا مسئلهٔ مشابهی را در زمان اجرای کمتر حل می‌کند، اما در آن الگوریتم می‌بایست وزن یال‌ها اعداد نامنفی باشند. بنابراین در عمل الگوریتم بلمن-فورد فقط برای گراف‌هایی که یال با وزن منفی دارند استفاده می‌شود. قبل از توضیح الگوریتم لازم به ذکر است که اگر گراف دوری با مجموع وزن منفی داشته باشد که از مبدأ قابل دست‌یابی باشد، مسئلهٔ کوتاهترین مسیر جوابی نخواهد داشت، چراکه با پیمایش آن دور به هر تعداد بار دلخواه، مسیرهایی با وزن کمتر و کمتر حاصل خواهد شد. اجرای الگوریتم 1-|V| دنبالهٔ چنان تعریف می‌شود که برای هر رأس ، مقدار در پایان مرحلهٔ ام برابر وزن کوتاهترین گذر از مبدأ به است با این شرط اضافه که تعداد یال‌های این گذر حداکثر باشد. بنابراین در پایان مرحلهٔ (1-|V|)ام برابر وزن کوتاهترین مسیر از مبدأ به خواهد بود (در واقع چون دور با مجموع وزن منفی نداریم، کوتاهترین گذر با حداکثر 1-|V| یال از مبدأ به ، همان کوتاهترین مسیر از مبدأ به در گراف خواهد بود). با این اوصاف اگر آزادسازی همهٔ یال‌ها را برای بار |V|ام هم تکرار کنیم و بعد از این مرحله هم دنبالهٔ تغییر کند، آنگاه می‌توان نتیجه گرفت که گراف دور منفی‌ای دارد که از مبدأ قابل دست‌یابی است. الگوریتم همانطور که گفته شد الگوریتم بلمن-فورد توانایی تشخیص دور منفی را نیز دارد. | ## بخش 2: الگوریتم بلمن–فورد | بنابراین الگوریتم را به گونه‌ای پیاده‌سازی می‌کنند که در صورت تشخیص دور منفی مثلاً مقدار بولی True برگرداند. برای قسمت دوم، طول کوتاه‌ترین مسیر از مبنا به u با حداکثر تعداد i یال را در نظر بگیریم. فرض کنیم v گرهی قبل از u در طول این مسیر باشد، در اینصورت کوتاه‌ترین مسیر به v با تعداد i-1 یال است. بنابه فرض استقرا بعد از i-1 تکرار حلقه، کوتاه‌ترین مسیر تا v حداکثر به طول همین مسیر است(با i-1 یال). توجه کنید که در چنین درختی که مسیر شامل حلقه نداریم، حداکثر طول مسیر برابر با است. پیچیدگی زمانی مشخص است که در مرحله، در هر مرحله عملیات بر روی یال‌ها انجام می‌شود. برای مثال پروتکل RIP یکی از الگوریتم‌هایی است که انتشار یافته‌است چون تعدادی از گره‌ها (مسیر یاب ها) را با یک سیستم خود مختار درگیر می‌کند. | ## بخش 3: الگوریتم بلمن–فورد | یک مجموعه شبکه IP که معمولاً به وسیلهٔ یک ISP مالکیت می‌شود شامل این گام‌ها می‌شود: ۱- هر گره مسافت بین خودش و تمام گره‌هایی که در داخل AS اند را محاسبه می‌کند و در جدولی اطلاعات را ذخیره می‌کند . ۳- وقتی یک گره جدول مسافت را از گره مجاور خودش دریافت می‌کند، کوتاهترین مسیرها را به تمام بقیه گره‌ها محاسبه می‌کند و جدول خودش را برای بازتاب تغییرات بروز می‌کند. اشکال اصلی الگوریتم بل من فورد در این تنظیمات عبارتست از : - به‌خوبی مقیاس (نسبت) نمی‌کند. - تغییر در توپولوژی شبکه به سرعت انعکاس داده نمی‌شود چون آپدیت شدن گره به گره منتشر می‌شود. - محاسبه تا بی‌نهایت ( اگر لینک یا گره در انتقال به یک گره غیرقابل دسترس از بعضی از مجموعه دیگر گره‌ها شکست بخورد، آن گره‌ها ممکن است برای همیشه به تدریج تخمین مسافتشان به آن گره افزایش پیدا کند و در ضمن ممکن است مسیر loop باشد.) توسعه YEN در انتشار سال ۱۹۷۰، Jin.Y.Yen یک توسعه از الگوریتم بل من فورد را برای گراف بدون حلقه با وزن منفی تشریح کرد. توسعه Yen ابتدا کمی نوبت خطی انحصاری بر روی تمام رئوس و بعد تمام قسمت‌های مجموعه تمام یال‌ها در یکی از ۲ زیر مجموعه نشان داد. هر راس بعدی که در ترتیب v|V|، v|V|−۱، ...، v۱ ملاقات می‌شود، هر خروجی از آن راس را در Eb کم می‌کند . | ## جمع‌بندی | توسعه Yen، تأثیرگذاری بسزایی در نصف کردن تعداد مسیرهای طی شده مورد نیاز برای مسئله کوتاهترین مسیر ممکن تک منبعی داشت.