الگوریتم جانسون الگوریتمی برای پیدا کردن کوتاهترین مسیر بین تمام جفت های راسی در گرافهای پراکنده جهت دار است. الگوریتم اجازه می دهد که وزن بعضی از یال های گراف منفی باشد، ولی نباید دوری با وزن منفی وجود داشته باشد. این الگوریتم از الگوریتم بلمن - فورد بهره جسته تا گراف جدیدی بسازد که در آن تمام وزن های منفی گراف حذف شده؛ و سپس از الگوریتم دیکسترا در گراف جدید استفاده می کند. نام این الگوریتم از دونالد بی جانسون*[ ۱] کسی که اولین بار در سال ۱۹۷۷ این تکنیک را منتشر کرد، گرفته شده است.
الگوریتم جانسون شامل مراحل زیر می باشد.
• یک گره 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 محاسبه شد، تمام طول های یال های تغییر یافته منفی نیستند و بهینه بودن مسیری که در الگوریتم دیکسترا پیدا شده مورد اطمینان است. مسافت را می توان از روی مسافت حساب شده در الگوریتم دیکسترا در گراف وزن دهی مجدد به وسیلهٔ بالعکس کردن تبدیل وزن دهی مجدد محاسبه کرد.
پیچیدگی زمان این الگوریتم با استفاده کردن از هیپ فیبوناتچی در اجرای الگوریتم دیکسترا O ( | V | 2 log | V | + | V | | E | ) می باشد: این الگوریتم زمان O ( | V | | E | ) را برای قسمت بلمن - فورد و O ( | V | log | V | + | E | ) را برای هر | V | بار اجرای الگوریتم دیکسترا مصرف می کند. بنابراین موقعی که گراف پراکنده است، زمان کل می تواند سریع تر از الگوریتم فلوید - وارشال باشد که همان مسئله را در زمان O ( V 3 ) حل می کند.
این نوشته برگرفته از سایت ویکی پدیا می باشد، اگر نادرست یا توهین آمیز است، لطفا گزارش دهید: گزارش تخلفالگوریتم جانسون شامل مراحل زیر می باشد.
• یک گره 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 محاسبه شد، تمام طول های یال های تغییر یافته منفی نیستند و بهینه بودن مسیری که در الگوریتم دیکسترا پیدا شده مورد اطمینان است. مسافت را می توان از روی مسافت حساب شده در الگوریتم دیکسترا در گراف وزن دهی مجدد به وسیلهٔ بالعکس کردن تبدیل وزن دهی مجدد محاسبه کرد.
پیچیدگی زمان این الگوریتم با استفاده کردن از هیپ فیبوناتچی در اجرای الگوریتم دیکسترا O ( | V | 2 log | V | + | V | | E | ) می باشد: این الگوریتم زمان O ( | V | | E | ) را برای قسمت بلمن - فورد و O ( | V | log | V | + | E | ) را برای هر | V | بار اجرای الگوریتم دیکسترا مصرف می کند. بنابراین موقعی که گراف پراکنده است، زمان کل می تواند سریع تر از الگوریتم فلوید - وارشال باشد که همان مسئله را در زمان O ( V 3 ) حل می کند.
wiki: الگوریتم جانسون