برای یافتنِ کوتاه‌ترینِ مسیرِ همهٔ جفت‌ها در گرافِ دارایِ یالِ منفی، نمی‌توان هر وزن را با یک ثابت مثبت کرد و همان مسیرها را انتظار داشت. Johnson از پتانسیلِ رأس‌ها استفاده می‌کند تا هزینهٔ همهٔ مسیرهایِ یک زوج به اندازهٔ یکسان تغییر کند. سپس Dijkstra رویِ وزن‌هایِ نامنفی اجرا و فاصلهٔ اصلی بازیابی می‌شود.
یالِ منفی هست، دورِ منفی نداریم
گرافِ اصیل پنج رأسِ A، B، C، D و U دارد. یال‌ها AB=۲، BC=−۴، CD=۲، AD=۱ و DB=۳ هستند؛ U جداست. چرخهٔ B→C→D→B هزینهٔ ۱ دارد و منفی نیست. برای A به D، مسیرِ مستقیم ۱ اما A→B→C→D هزینهٔ ۰ دارد.
اگر به هر یال ۴ اضافه کنیم، مسیرِ مستقیم ۵ و مسیرِ سه‌یاله ۱۲ می‌شود؛ رتبهٔ مسیرها عوض شده است. این مسیرِ غلط واقعاً با شمارشِ مستقل محاسبه می‌شود. یک ثابت به‌ازایِ یال، مسیرِ دارایِ یال‌هایِ بیشتر را بیشتر جریمه می‌کند.
پتانسیل را از مبدأِ کمکی بگیریم
مبدأِ کمکی با یالِ صفر به همهٔ رأس‌ها متصل تصور می‌شود. در کد، آغازِ همهٔ فاصله‌ها با صفر دقیقاً همین قرارداد را پیاده می‌کند و Bellman–Ford اجرا می‌شود. حاصل h(A)=۰، h(B)=۰، h(C)=−۴، h(D)=−۲ و h(U)=۰ است؛ راسِ جدا هم پتانسیلِ متناهی دارد.
وزنِ تازهٔ u→v برابر w(u,v)+h(u)−h(v) است. برای گرافِ ما، وزن‌ها به‌ترتیبِ AB، BC، CD، AD و DB برابر ۲، ۰، ۰، ۳ و ۱ می‌شوند. همه نامنفی‌اند؛ اکنون شرطِ اجرایِ Dijkstra برای همین گراف برقرار است.
چرا مسیرِ بهینه حفظ می‌شود؟
در جمعِ هزینهٔ یک مسیر، h رأس‌هایِ داخلی یک‌بار مثبت و یک‌بار منفی ظاهر می‌شوند و حذف می‌شوند. تنها h مبدأ−h مقصد می‌ماند. پس همهٔ مسیرهایِ بینِ دو رأسِ ثابت، به اندازهٔ یکسان جابه‌جا می‌شوند؛ این ویژگی را افزودنِ ۴ به هر یال نداشت.
| مسیرِ A به D | هزینهٔ اصلی | پس از پتانسیل |
|---|---|---|
| A→D | ۱ | ۳ |
| A→B→C→D | ۰ | ۲ |
در هر دو سطر، اختلافِ هزینه ۲ است. کد دو جمعِ مسیر را مستقل از Dijkstra با خودِ فهرستِ یال‌ها حساب و رابطهٔ تلسکوپی را کنترل می‌کند. بنابراین نامنفی‌شدنِ وزن تنها شاهدِ صحتِ تبدیل نیست.
فاصلهٔ همهٔ جفت‌ها را برگردانیم
از هر رأس، Dijkstra با heap رویِ وزن‌هایِ تازه اجرا می‌شود. فاصلهٔ اصلی d(s,t)=d′(s,t)−h(s)+h(t) است. برای A به D، فاصلهٔ تازه ۲ و بازیابی ۲−۰−۲=۰ می‌شود. مقصدِ نرسیدنی با None ثبت می‌شود، نه با فاصلهٔ صفر.
تمام ۲۵ زوج با مرجعِ مستقلِ شمارشِ همهٔ مسیرهایِ سادهٔ همان گراف برابرند. این oracle برای پنج رأس مناسب است و راهِ مقیاس‌پذیرِ عمومی نیست. فاصلهٔ هر رأس به خودش ۰ است، ولی برای رسیدن از A به U یا از U به A مسیر نداریم؛ JSON این تفاوت را حفظ می‌کند.
دورِ منفیِ بخشِ دیگر هم مانع است
در دو شاهدِ نامعتبر، یکی در مؤلفهٔ اصلی و دیگری در بخشی جدا از A دورِ منفی ساخته می‌شود. الگوریتمِ همه‌جفت‌ها هر دو را رد می‌کند؛ اتصالِ صفرِ مبدأِ کمکی سبب می‌شود دورِ جدا هم از پیش‌بررسی پنهان نماند. این قرارداد با پرسشِ تک‌مبدأِ محدود به بخشِ قابلِ دسترسی فرق دارد.
در مجموع هفت حالتِ نامعتبر، از رأسِ ناشناخته و یالِ تکراری تا bool به‌جایِ وزن، selfloop و بودجهٔ بیش از ۶ رأس رد می‌شوند. وزن‌ها صحیح و با قدرِ حداکثر ۲۰ و حداکثر ۱۶ یال‌اند. کتابخانهٔ گراف، شبکهٔ واقعی یا سنجشِ سرعت اجرا نشده است.
Bellman–Ford شاهدِ دورِ منفی و Dijkstra مسیرِ تک‌مبدأِ نامنفی را توضیح می‌دهد؛ اینجا تبدیل و بازیابیِ همهٔ جفت‌ها موضوع است. ادامه در مبانی هوش مصنوعی؛ این وزن‌ها تعرفه، تأخیرِ تماس یا مسیرِ داخلیِ اپرا نیستند.
فایل تمرین و منبع
کد کاملِ تمرینِ مستقل و کنترل‌ها؛ Python · ورودی و تمامِ خروجیِ اجرای واقعی؛ JSON
منابع در 2026-11-04 خوانده شدند؛ این تاریخ، تاریخ انتشار منبع نیست. مثال‌ها و فایل‌های این راهنما آموزشی و ساختهٔ تحریریه‌اند.