الگوریتم جانسون

الگوریتم جانسون شامل مراحل زیر می‌باشد.

• یک گره q جدید به گراف اضافه و به وسیله یال وزن صفر به گره‌ها ی دیگر متصل شود.
• از الگوریتم بلمن- فورد استفاده شود برای پیدا کردن هر راس v با کمترین وزن( h(v در مسیر q تا v باید از راس q شروع کنیم. اگر این مرحله یک طوقهٔ منفی را نشان داد، الگوریتم پایان یافته‌است.
• یال‌های گراف اصلی با استفاده از مقدارهای محاسبه شده به وسیله الگوریتم بلمن-فورد دوباره وزن دهی شوند : یک یال از از u تا v با طول (w(u,v طول جدید (w(u,v) + h(u) −h(v را می‌دهد.
• برای هر گرهٔ s، الگوریتم دیکسترا برای پیدا کردن کمترین مسیر، ازs تا هر راس دیگر در گراف وزن دهی مجدد استفاده می‌شود. در مسیر گراف دهی مجدد، تمام مسیرهای بین جفت گره‌ها، کمیت مشابه (h(s) -h(t به آنها اضافه می‌شود بنابر این مسیری که کوتاهترین در گراف اصلی باشد در گراف تغییر داده شده هم کمترین باقی می‌ماند و بالعکس.

به هر حال، به خاطر راهی که مقدار (h(v محاسبه شد، تمام طول‌های یال‌های تغییر یافته منفی نیستند و بهینه بودن مسیری که در الگوریتم دیکسترا پیدا شده مورد اطمینان است. مسافت را می‌توان از روی مسافت حساب شده در الگوریتم دیکسترا در گراف وزن دهی مجدد به وسیلهٔ بالعکس کردن تبدیل وزن دهی مجدد محاسبه کرد.

پیچیدگی زمان این الگوریتم با استفاده کردن از هیپ فیبوناتچی در اجرای الگوریتم دیکسترا ${\displaystyle O(|V{|}^2\log |V|+|V||E|)}$

سه مرحله اول الگوریتم جانسون در شکل‌های زیر ترسیم شده‌است گراف سمت چپ دو یال منفی دارد اما هیچ طوقهٔ منفی ندارد. در مرکز، راس جدید q نشان داده شده است که کوتاهترین مسیر درخت که بوسیله الگوریتم بالمن-فورد محاسبه شده با q ، بعنوان راس شروع کننده ومقدار ( h(v که در هر گره دیگر به عنوان طول کوتاهترین مسیر از q تا آن گره محاسبه شده‌است. توجه کنید این مقدارها همه مثبت نیستند، به دلیل اینکه q، یال با طول صفر برای هر راس دارد و کوتاهترین مسیر نمی‌تواند بلند تر از آن یال باشد. در شکل سمت راست گراف وزن دهی مجدد نشان داده شده که به وسیلهٔ (w(u,v) + h(u) −h(v تشکیل شده‌است.در این گراف وزن دهی مجدد، تمام وزن‌های یال منفی نیستند .اما کوتاهترین مسیر بین هر دو گره از همان ترتیب گره‌ها استفاده می‌کند که کوتاهترین مسیر بین همان دو گراف اصلی استفاده شده‌است.

• www.quadibloc.com