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

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

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

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

پیمایش گراف و پیمایش درخت
هرس آلفا بتا A* الگوریتم *B Beam الگوریتم بلمن–فورد جستجوی ابتدا بهترین جستجوی دوجهته الگوریتم جستجوی اول سطح D* الگوریتم جستجوی عمق اول جستجوی عمق محدود الگوریتم دیکسترا الگوریتم فلوید-وارشال الگوریتم تپه‌نوردی جستجوی عمق اول عمیق‌کننده تکراری الگوریتم جانسون Lexicographic breadth-first Uniform-cost رده:الگوریتم‌های جستجو
جستار وابسته
برنامه‌ریزی پویا Search games

توضیح الگوریتم

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

• یک گره 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 تشکیل شده‌است.در این گراف وزن دهی مجدد، تمام وزن‌های یال منفی نیستند .اما کوتاهترین مسیر بین هر دو گره از همان ترتیب گره‌ها استفاده می‌کند که کوتاهترین مسیر بین همان دو گراف اصلی استفاده شده‌است.

پانویس

1. Donald B. Johnson

منابع

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