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

الگوریتم جانسون برای پیدا کردن کوتاه ترین مسیر بین هر جفت راس در گراف وزن دار (وزن یالها میتواند منفی باشد ولی دور منفی نباید وجود داشته باشد) و جهت دار به کار می‌رود.

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

سه مرحله‌ی اول الگوریتم در مثال زیر آمده است:

لم ۱: در گراف ساخته شده پس از اجرای الگوریتم بلمن-فورد، به همه مسیرهای بین دو راس $s$ و $t$ مقدار ثابت $h(s)-h(t)$ اضافه شده است.

اثبات : $p$ مسیر بین $s$ و $y$ است. وزن این مسیر در گراف جدید برابر است با: $(w(s,p_1) + h(s) – h(p_1)) + (w(p_1,p_2) + h(p_1) – h(p_2)) + … + (w(p_n,t) + h(p_n) – h(t))$

همه‌ی $+h(p_i)$ ها با $-h(p_i)$ که در پرانتز بعدی آمده است خنثی میشود و در نهایت وزن این مسیر برابر است با: $w(s,p_1) + w(p_1,p_2) + … + w(p_n,t) + h(s) – h(t)$ که همان وزن این مسیر در گراف اصلی به اضافه $ h(s)-h(t)$ است.

طبق لم ۱ چون به همه مسیرهای دو راس یک مقدار ثابت اضافه میشود، پس مسیری در گراف اولیه کوتاه ترین است اگر و تنها اگر در گراف جدید کوتاه ترین مسیر باشد.

بنابراین کوتاه ترین مسیر ها تغییر نمیکنند و با اجرای الگوریتم دایکسترا برای هر راس در گراف جدید، کوتاه ترین مسیر بین هر دو راس را در گراف اولیه هم بدست می ‌آوریم و برای بدست آوردن وزن کوتاه ترین مسیر بین $s$ و $t$ تنها کافی است مقدار $h(s)-h(t)$ را از وزن کوتاه ترین مسیر بدست آمده در گراف جدید کم کنیم تا مقدار واقعی بدست آید.

در این الگوریتم یک بار الگوریتم بلمن-فورد که پیچیدگی زمانی آن $O(VE)$ است و به تعداد راس ها الگوریتم دایکسترا (که اگر از هیپ فیبوناچی استفاده کنیم پیچیدگی آن $O(VlogV + E)$ خواهد بود) اجرا میشود.

بنابراین در نهایت پیچیدگی زمانی الگوریتم جانسون $O(V^2logV + VE)$ میشود. اگر گراف کامل باشد $E$ برابر $O(V^2)$ خواهد بود و پیچیدگی الگوریتم جانسون برابر با الگوریتم فلوید-وارشال میشود.

در گراف هایی که یالهای کمتری دارند الگوریتم جانسون بسیار بهتر از الگوریتم فلوید-وارشال برای پیدا کردن تمام زوج کوتاه ترین مسیرها عمل میکند.