raha_hakhamanesh
چهارشنبه 08 فروردین 1386, 14:12 عصر
درباره الگوریتم دیکسترا(دایجسترا)
این الگوریتم که عنوانش را از ابداع کننده آن یعنی دیکسترا هلندی گرفته است کوتاهترین مسیر در یک گراف همبند ، جهت دار و وزن دار با وزن غیر منفی را بدست می آورد .
بطور مثال اگر تعدادی شهر را به وسیله یک گراف نشان دهیم و فاصله بین شهرها را بوسیله یالهای گراف نشان دهیم بطوریکه می دانیم فاصله بین دو شهر یک عدد مثبت است آنگاه می توان با استفاده از الگوریتم دیکسترا کوتاهترین مسیر بین دو شهر را بدست آورد .
این الگوریتم کوتاهترین فاصله بین مبدا با سایر شهرها را بدست می آورد و نمی تواند کوتاهترین فاصله بین هر دو نقطه دلخواه را بدست آورد(مگر آنکه بر روی همه مسیرها آن را اعمال کنیم) و یا نمی تواند گراف با یالهای دارای وزن منفی را پردازش کند برای این منظور باید از الگوریتم هایی نظیر فلوید- وارشال و بلمن- فورد استفاده نمایید . (در آینده به این الگوریتم ها نیز اشاره خواهم کرد)
شبه کد الگوریتم دیکسترا در زیر ارائه شده است
DIJKSTRA(G , W , S)
Initialize single-source ( G , S )
S={ }
Q=V[G]
While Q <> { } do
U = Extract-Min Q
S = S + {u}
For each vertex V member of ADJ[u] do
Relax (u , v , w)
توضیح بیشتر
در این الگوریتم دو مجموعه S,Q وجود دارد . مجموعه S شامل همه رئوس است این مجموعه برای آن است که ما به مقادیر ADJ[u] که همان هزینه کوتاهترین مسیر است نیاز داریم . مجموعه Q نیز شامل همه رئوس است .
مجموعه S در ابتدا تهی می باشد و در هر گام یک عضو (راس) از مجموعه Q به مجموعه S انتقال می یابد ، این راس انتقال یافته در واقع همان راسی است که فاصله تا آن راس ، کمترین مقدار می باشد .
مرتبه اجرایی الگوریتم دیکسترا
این الگوریتم در پیاده سازی و بدست آوردن زمان مصرفی می تواند ساختار متفاوتی از خود نشان دهد اما اگر در پیاده سازی این الگوریتم از ساختارماتریس اسپارس و هرم-دوجمله ای (binary heap) استفاده نماییم و برای نگهداری مسیر از صف (Queue) بهره ببریم آنگاه زمان مصرفی این الگوریتم به حداقل مقدار خود یعنی (|O( ( |V| + |E| )* Log|V خواهد رسید . توجه شود اگر ساختار پیاده سازی از ماتریس اسپارس و هرم – دوجمله ای مینیمم استفاده نکند مرتبه زمانی به مقدار (O(V^2 + E) = O(V^2 خواهد رسید .
برگرفته از مقاله م.جم پور CIS2006 با تلخیص
موفق باشید
این الگوریتم که عنوانش را از ابداع کننده آن یعنی دیکسترا هلندی گرفته است کوتاهترین مسیر در یک گراف همبند ، جهت دار و وزن دار با وزن غیر منفی را بدست می آورد .
بطور مثال اگر تعدادی شهر را به وسیله یک گراف نشان دهیم و فاصله بین شهرها را بوسیله یالهای گراف نشان دهیم بطوریکه می دانیم فاصله بین دو شهر یک عدد مثبت است آنگاه می توان با استفاده از الگوریتم دیکسترا کوتاهترین مسیر بین دو شهر را بدست آورد .
این الگوریتم کوتاهترین فاصله بین مبدا با سایر شهرها را بدست می آورد و نمی تواند کوتاهترین فاصله بین هر دو نقطه دلخواه را بدست آورد(مگر آنکه بر روی همه مسیرها آن را اعمال کنیم) و یا نمی تواند گراف با یالهای دارای وزن منفی را پردازش کند برای این منظور باید از الگوریتم هایی نظیر فلوید- وارشال و بلمن- فورد استفاده نمایید . (در آینده به این الگوریتم ها نیز اشاره خواهم کرد)
شبه کد الگوریتم دیکسترا در زیر ارائه شده است
DIJKSTRA(G , W , S)
Initialize single-source ( G , S )
S={ }
Q=V[G]
While Q <> { } do
U = Extract-Min Q
S = S + {u}
For each vertex V member of ADJ[u] do
Relax (u , v , w)
توضیح بیشتر
در این الگوریتم دو مجموعه S,Q وجود دارد . مجموعه S شامل همه رئوس است این مجموعه برای آن است که ما به مقادیر ADJ[u] که همان هزینه کوتاهترین مسیر است نیاز داریم . مجموعه Q نیز شامل همه رئوس است .
مجموعه S در ابتدا تهی می باشد و در هر گام یک عضو (راس) از مجموعه Q به مجموعه S انتقال می یابد ، این راس انتقال یافته در واقع همان راسی است که فاصله تا آن راس ، کمترین مقدار می باشد .
مرتبه اجرایی الگوریتم دیکسترا
این الگوریتم در پیاده سازی و بدست آوردن زمان مصرفی می تواند ساختار متفاوتی از خود نشان دهد اما اگر در پیاده سازی این الگوریتم از ساختارماتریس اسپارس و هرم-دوجمله ای (binary heap) استفاده نماییم و برای نگهداری مسیر از صف (Queue) بهره ببریم آنگاه زمان مصرفی این الگوریتم به حداقل مقدار خود یعنی (|O( ( |V| + |E| )* Log|V خواهد رسید . توجه شود اگر ساختار پیاده سازی از ماتریس اسپارس و هرم – دوجمله ای مینیمم استفاده نکند مرتبه زمانی به مقدار (O(V^2 + E) = O(V^2 خواهد رسید .
برگرفته از مقاله م.جم پور CIS2006 با تلخیص
موفق باشید