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

رده	مسئله یافتن کوتاهترین مسیر (for weighted graphs)
ساختمان داده	گراف (ساختار داده)
کارایی بدترین حالت	${\displaystyle O(|V|^{2}\log |V|+|V||E|)}$

الگوریتم جانسون الگوریتمی برای پیدا کردن کوتاهترین مسیر بین تمام جفت‌های راسی در گرافهای پراکنده جهت دار است. الگوریتم اجازه می‌دهد که وزن بعضی از یال‌های گراف منفی باشد، ولی نباید دوری با وزن منفی وجود داشته باشد. این الگوریتم از الگوریتم بلمن-فورد بهره جسته تا گراف جدیدی بسازد که در آن تمام وزن‌های منفی گراف حذف شده؛ و سپس از الگوریتم دیکسترا در گراف جدید استفاده می‌کند. نام این الگوریتم از دونالد بی جانسون*^[۱] کسی که اولین بار در سال ۱۹۷۷ این تکنیک را منتشر کرد، گرفته شده‌است.

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

• یک گره 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|)}$ می‌باشد: این الگوریتم زمان ${\displaystyle O(|V||E|)}$ را برای قسمت بلمن-فورد و${\displaystyle O(|V|\log |V|+|E|)}$ را برای هر ${\displaystyle |V|}$ بار اجرای الگوریتم دیکسترا مصرف می‌کند. بنابراین موقعی که گراف پراکنده‌ است، زمان کل می‌تواند سریع‌تر از الگوریتم فلوید-وارشال باشد که همان مسئله را در زمان ${\displaystyle O(V^{3})}$ حل می‌کند.

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

• مشارکت‌کنندگان ویکی‌پدیا. «Johnson's algorithm». در دانشنامهٔ ویکی‌پدیای انگلیسی، بازبینی‌شده در ۳۱ می ۲۰۱۱.
• www.quadibloc.com