المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


آموزش:الگوریتم‌های تکمیلی:الگوریتم جانسون

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

تعریف

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

الگوریتم

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

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


ابزار صفحه