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

===== تعریف =====

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

===== الگوریتم =====

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

===== مثال =====

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

{{ :آموزش:الگوریتم‌های_تکمیلی:johnson_salgorithm.png |}}

===== اثبات درستی =====

**لم ۱:** در گراف ساخته شده پس از اجرای الگوریتم بلمن-فورد، به همه مسیرهای بین دو راس $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)$ خواهد بود و پیچیدگی الگوریتم جانسون برابر با [[آموزش:الگوریتم:الگوریتم_فلوید-وارشال|الگوریتم فلوید-وارشال]] میشود.

در گراف هایی که یالهای کمتری دارند الگوریتم جانسون بسیار بهتر از [[آموزش:الگوریتم:الگوریتم_فلوید-وارشال|الگوریتم فلوید-وارشال]] برای پیدا کردن تمام زوج کوتاه ترین مسیرها عمل میکند.