وجودِ یالِ منفی به‌تنهایی به معنیِ نبودِ کوتاه‌ترینِ مسیر نیست. مشکلِ دیگر،چرخهٔمنفیِ قابل‌دسترسی ازمبدأ است؛ با تکرارِ آن می‌توان هزینه را باز هم کم کرد. این تمرینِ بلمن–فورد سه گرافِ اصیل را جدا اجرا می‌کند: یالِ منفیِ بی‌چرخه،چرخهٔمنفیِ قابل‌دسترسی وچرخهٔمنفی درمؤلفهٔجدا.
یک یالِ منفی،یک جوابِ محدود
گره‌هایِ A،B،C،D وU داریم. یال‌هایِ جهت‌دارA→B با۴،A→C با۵،B→C با−۲،C→D با۳ وB→D با۱۰ هستند. U جداست. ازA،هزینهٔB برابر۴،C برابر۲ وD برابر۵ می‌شود؛ مسیرِ D همانA→B→C→D است. یالِ منفیِ B→C بخشی ازیک جوابِ محدود ودرست است.
کد،distِ مبدأ را۰ وبرایِ گره‌هایِ هنوز‌نرسیده None می‌گذارد. هر یال فقط وقتی نامزد می‌سازد که مبدأِ آن دسترس‌پذیر باشد. هزینهٔبهتر،فاصله وpredecessor را اصلاح می‌کند؛ تساویِ هزینه دراین قرارداد parent را عوض نمی‌کند. بعد ازپایان،مسیرِ هرگرهِ دسترس‌پذیر ازهمان دفتر بازسازی می‌شود.
جاروبِ یال‌ها و دورِ اضافی
اجرایِ اصیلِ ما درهرجاروب همهٔیال‌ها را به‌ترتیبِ اعلام‌شده بررسی می‌کند و مقدارهایِ تازه درهمان دور قابل‌استفاده‌اند. حداکثرِ V−1 جاروب برایِ مرزِ مسیرِ ساده داریم ویک دورِ اضافی برایِ تشخیصِ ادامهٔبهبود. اگر دریک دور هیچ تغییری نبود،زودتر متوقف می‌شویم. این دفتر با اجرایِ هم‌زمانِ برپایهٔنسخهٔقبلی یکی نیست ومواردِ میانی باید باهمین ترتیب خوانده شوند.
برایِ گرافِ اول،oracleِ جدا همهٔمسیرهایِ سادهٔکوچک ازA را می‌شمارد وکمترینِ هزینهٔهرمقصد را می‌گیرد. کلِ بردارِ نتیجه برابر است: A=۰،B=۴،C=۲،D=۵ وU=None. عددِ صفر را برایِ U نساخته‌ایم؛ نرسیدن با مسیرِ صفر‌یالیِ مبدأ فرق دارد.
چرخهٔقابل‌دسترسی چرا جواب را عوض می‌کند؟
گرافِ دوم یال‌هایِ A→B با۴،B→C با−۳،C→B با۱ وC→D با۲ دارد. چرخهٔB→C→B وزنِ−۲ دارد. برنامه در دورِ اضافی هنوز بهبود می‌بیند،با چندگامِ predecessor واردِ خودِ چرخه می‌شود ویال‌هایِ آن را به‌ترتیبِ واقعی بازسازی می‌کند. شاهدِ این اجرا C→B→C ووزنش−۲ است.
راهِ سادهٔA→B→C هزینهٔ۱ دارد. صفر،یک،دو وسه بار تکرارِ شاهدِ چرخه،هزینه‌هایِ ۱،−۱،−۳ و−۵ را می‌سازد. همهٔیال‌هایِ شاهد درورودی وجود دارند وجمعِ وزنِ آن‌ها دوباره کنترل می‌شود؛ فقط پرچمِ«چرخه پیدا شد» را شاهدِ کامل ننامیده‌ایم.
| fixture | چرخهٔمنفیِ قابل‌دسترسی؟ | نتیجهٔگزارش |
|---|---|---|
| یالِ منفیِ گرافِ اول | خیر | فاصله‌هایِ محدود باoracle برابر |
| چرخهٔB↔C درگرافِ دوم | بله | شاهدِ وزنِ−۲؛بردارِ نهایی اعلام نمی‌شود |
| چرخه درمؤلفهٔجدا | خیر،ازA نمی‌رسیم | گره‌هایِ جدا None می‌مانند |
عددهایِ میانی را فاصلهٔنهایی ننامیم
درحالتِ چرخهٔقابل‌دسترسی،دفترِ جاروب‌ها برایِ توضیح باقی می‌ماند،اما distancesِ نهایی None وfinite_distance_vector_valid برابرِ False است. این نسخه تمامِ بردارِ پاسخِ محدود را رد می‌کند؛ دربارهٔرأس‌هایی که شاید خارج ازدامنهٔاثرِ چرخه باشند نتیجهٔتازهٔاثبات‌نشده نمی‌دهد.
گرافِ سوم فقطA→B با۴ وچرخهٔC→D با−۳ وD→C با۱ دارد. ازA راهی بهC وD نیست؛ بنابراین الگوریتم برایِ مبدأِ A چرخهٔمنفیِ قابل‌دسترسی گزارش نمی‌کند وC،D وU نامعلوم می‌مانند. این به معنیِ نبودِ چرخه درکلِ گراف نیست؛ سؤالِ اجرایِ ما به دسترسی ازمبدأ وابسته است.
با دایکسترا یا معادلهٔبلمن یکی نگیریم
دایکسترا درقراردادِ صفحهٔموجود وزنِ منفی را ازابتدا رد می‌کند؛ اینجا یالِ منفی را باچرخهٔمنفی تفکیک کرده‌ایم. Value Iterationِ مدلِ احتمالی هم انتظارِ پاداشِ تنزیل‌شده وبیشینهٔعمل را دارد؛ نامِ مشترکِ بلمن این دو هدف را یکی نمی‌کند.
فایل فقط گراف‌هایِ کوچکِ جهت‌دار باوزنِ صحیحِ محدود را اجرا می‌کند؛ Java وNetworkX اجرا نشده‌اند،شبکهٔواقعی وبهینه‌سازیِ مسیرِ عملیاتی هم نداریم. برای ادامه به مبانی هوش مصنوعی بروید ونوعِ وزن،مبدأ وشاهدِ نبودِ پاسخِ محدود را کنارِ نتیجه ثبت کنید؛ این آموزش روشِ داخلیِ اپرا را معرفی نمی‌کند.
فایل تمرین و منبع
کد مستقلِ تمرینِ محدود · تمام خروجیِ واقعیِ همین تمرین؛ JSON
- مرجعِاصلیِSedgewick/Wayne؛ مسیر وشاهدِچرخهٔمنفیِقابل‌دسترسی؛ بخش‌هایِتعریف،نه اجرایِJavaِصف‌محور
- NetworkX؛ وزنِمنفی،گره‌هایِدسترس‌پذیر ومؤلفهٔجدا؛ کتابخانه اجرا نشده است
منابع در 2026-11-04 خوانده شدند؛ این تاریخ، تاریخ انتشار منبع نیست. مثال‌ها و فایل‌های این راهنما آموزشی و ساختهٔ تحریریه‌اند.