الگوریتم دیکسترا

از ویکی‌پدیا، دانشنامهٔ آزاد

در نظریه گراف، الگوریتم دَیکسترا یکی از الگوریتم‌های پیمایش گراف است که توسط دانشمند هلندی علوم رایانه، اِدْسْخِر دَیْکْسْترا در سال ۱۹۵۹ ارایه شد.

این الگوریتم یکی از الگوریتم‌های پیمایش گراف است که مسئلهٔ کوتاه‌ترین مسیر از مبدأ واحد را برای گراف‌های وزن‌داری که یال با وزن منفی ندارند، حل می‌کند و در نهایت با ایجاد درخت کوتاه‌ترین مسیر، کوتاه‌ترین مسیر از مبدأ به همهٔ رأس‌های گراف را به دست می‌دهد. همچنین می‌توان از این الگوریتم برای پیدا کردن کوتاه‌ترین مسیر از مبدأ تا رأس مقصد به این ترتیب بهره جست که در حین اجرای الگوریتم به محض پیداشدن کوتاه‌ترین مسیر از مبدأ به مقصد، الگوریتم را متوقف کرد.

در صورتی که گراف یال با وزن منفی داشته باشد، این الگوریتم درست کار نمی‌کند و می‌بایست از الگوریتم‌های دیگر نظیر الگوریتم بلمن-فورد که پیچیدگی زمانی آنها بیشتر است استفاده کنیم.

خط مشی الگوریتم دیکسترا، مشابه با روش حریصانهٔ استفاده شده در الگوریتم پریم برای پیدا کردن زیر درخت فراگیر بهینه است.

[ویرایش] این الگوریتم چگونه کار می‌کند؟

در حین اجرای الگوریتم دو چیز به طور ضمنی نگهداری می‌شود. یکی مجموعهٔ S از رأس‌هایی که وزن کوتاه‌ترین مسیر از مبدأ تا آن‌ها مشخص شده و دیگری دنبالهٔ d که برای هر رأس v، مقدار d_v برابر وزن کوتاه‌ترین مسیر از مبدأ تا v است به شرطی که تمام رأس‌های این مسیر به جز v از رئوس داخل S باشند. S در ابتدا تهی و مقادیر d برای همهٔ رئوس به غیر از مبدأ بی‌نهایت است و مقدار آن برای مبدأ‌ صفر گذاشته می‌شود. الگوریتم در هر مرحله رأسی خارج S را که d برای آن کمترین است انتخاب و به مجموعهٔ S اضافه می‌کند و سپس مقادیر d را برای رئوس همسایهٔ آن رأس به‌روز می‌نماید. در صورتی که نیاز به تشکیل درخت کوتاه‌ترین مسیر باشد، الگوریتم می‌بایست دنبالهٔ π را که π_v پدر رأس v در درخت کوتاه‌ترین مسیر است، به همراه دنبالهٔ d به‌روز کند.

[ویرایش] الگوریتم

در پیاده‌سازی، برای اینکه مشخص کنیم چه رئوسی در مجموعهٔ S هستند، در هر مرحله رأسِ وارد شده به S را برچسب می‌زنیم.

[ویرایش] پیاده‌سازی

یک پیاده‌سازی نوعی به این شرح است:

‎

 ۱  Algorithm Dijkstra(G,s)
 ۲  Input : G=(V,E), s(the source vertex)
 ۳  Output : two sequence d and π
 ۴  begin
 ۵      for all vertices w do
 ۶          dw = 
 ۷          πw = NULL
 ۸      ds = ۰
 ۹      while there exists an unmarked vertex do
۱۰         let w be an unmarked vertex such that dw is minimum
۱۱         mark w
۱۲         for all edge (w,z) such that z is unmarked do
۱۳             if dw + weight(w,z) < dz then
۱۴                 dz = dw + weight(w,z)
۱۵                 πz = w
۱۶  end

[ویرایش] پیچیدگی زمانی

در ساده‌ترین پیاده‌سازی الگوریتمِ دیکسترا، داده‌ها در آرایه یا لیست پیوندی ذخیره می‌شوند که بدین ترتیب مینیمم مقدار d برای رئوس خارج S با الگوریتمی خطی یافت می‌شود. در این حالت پیچیدگی زمانی ( | O( | V | ² + | E خواهد بود، چراکه در گراف بدون جهت هر یال دقیقاً دوبار و در گراف جهت‌دار هر یال دقیقاً یک بار پیمایش می‌شود و هم‌چنین پیدا کردن مینیمم، (|O(|V زمان می‌خواهد که این مینیمم پیدا کردن |V| بار تکرار خواهد شد. برای گراف‌های پراکنده (یعنی گراف‌هایی که خیلی کمتر از مجذور |V| یال دارند) الگوریتم دیکسترا با نگهداری گراف در لیست مجاورت و استفاده از صف اولویت‌دار (Priority-Queue) (برای پیدا کردن مینیمم) با پیچیدگی زمانی ( | O(( | V | + | E | )log | V پیاده‌سازی می‌شود. در صورت استفاده از نگهدارندهٔ فیبوناتچی (Fibonacci heap) به جای صف اولویت‌دار، پیچیدگی زمانی با تحلیل جمعی (Amortized analysis) به ( | O( | E | + | V | log | V بهبود می‌یابد.

[ویرایش] کاربردها

• مسیریابی (Routing)

[ویرایش] پیوند به بیرون

• پیاده‌سازی الگوریتم دیکسترا در C#
• نمایش زندهٔ الگوریتم دیکسترا
• انیمیشن تعاملی الگوریتم دیکسترا برای کسانی که با الگوریتم آشنایی ندارند
• شبیه‌سازی الگوریتم دیکسترا با جاوا
• انیمیشن الگوریتم دیکسترا
• شبیه‌سازی الگوریتم دیکسترا
• مثال‌هایی از الگوریتم دیکسترا
• شبیه‌سازی الگوریتم دیکسترا
• شبیه‌سازی الگوریتم دیکسترا
• مثال‌هایی از الگوریتم دیکسترا

[ویرایش] منابع

‎