الگوریتم دایکسترا
- معرفیشده توسط
- Edsger W. Dijkstra
- سال
- 1956
- نوع
- algorithm
- خانواده
- Graph Algorithms
این متن ترجمه ماشینی است و هنوز بازبینی نشده است. متن اصلی را به انگلیسی بخوانید
چه کاری انجام میدهد؟
الگوریتم دایکسترا که توسط ادسخر دبلیو دایکسترا در سال ۱۹۵۶ معرفی شد، یکی از بنیادیترین الگوریتمها در علوم کامپیوتر برای حل مسئله کوتاهترین مسیر از یک مبدأ واحد است. این الگوریتم کوتاهترین مسیر را از یک رأس شروع به تمام رأسهای دیگر در یک گراف وزندار با وزن یالهای نامنفی پیدا میکند.
شهود پشت روش
این الگوریتم مجموعهای از رأسها را که کوتاهترین فاصلههای آنها از مبدأ از قبل مشخص شده است، حفظ میکند و به طور تکراری این مجموعه را با انتخاب نزدیکترین رأس پردازش نشده و بهروزرسانی فاصلهها به همسایگانش گسترش میدهد. نکته کلیدی، خاصیت حریصانه است: هنگامی که یک رأس انتخاب میشود، فاصله آن از مبدأ نهایی است زیرا تمام وزنهای یال نامنفی هستند، بنابراین هر مسیر طولانیتر از طریق رأسهای بازدید نشده نمیتواند کوتاهتر باشد. این امر صحت و بهینگی را تضمین میکند.
تاریخ
ادسخر دبلیو دایکسترا الگوریتم خود را در سال ۱۹۵۹ در مقالهای سه صفحهای منتشر کرد که به یکی از پر استنادترین آثار در علوم کامپیوتر تبدیل شد. این الگوریتم از کار دایکسترا بر روی کامپیوتر ARMAC در آمستردام نشأت گرفت. در طول دههها، بهبودهای بیشماری صورت گرفته است، از جمله ساختارهای داده بهتر (هیپهای فیبوناچی با پیچیدگی O(E+VlogV)) و انواع دوطرفه. این الگوریتم در پروتکلهای مسیریابی مدرن مانند OSPF در شبکهسازی مرکزی باقی مانده است.
چه زمانی استفاده شود
هنگام یافتن کوتاهترین مسیرها در گرافهایی با وزن یال نامنفی، از الگوریتم دایکسترا استفاده کنید. این الگوریتم برای سیستمهای ناوبری، مسیریابی شبکه و هر مسئله گراف که نیاز به مسیرهای بهینه دارد، ایدهآل است. از آن برای کوتاهترین مسیرهای مبدأ واحد به تمام رأسها استفاده کنید. برای گرافهایی با وزنهای منفی، به جای آن از بلمن-فورد استفاده کنید. برای جستجوی دوطرفه یا هدایت اکتشافی، الگوریتم A* را در نظر بگیرید.
محدودیتها و ملاحظات
- قادر به مدیریت گرافهایی با وزن یال منفی نیست
- کوتاهترین مسیرها را به تمام رأسها محاسبه میکند، نه فقط یک مقصد (اگرچه میتواند زودتر خاتمه یابد)
- کمتر از A* در صورت در دسترس بودن اطلاعات اکتشافی کارآمد است
- نیاز به کشف تمام رأسها دارد؛ برای اتصال بسیار پراکنده ناکارآمد است
شرایط منبع جایگزین بررسی علمی مستقل یا اعتبارسنجی توسط موتور تحلیل نیست.
نقاط قوت
- درک و پیادهسازی ساده با تضمینهای صحت واضح
- کارآمد با ساختارهای داده مناسب: O((V+E)logV) با هیپ دودویی، O(V²) با آرایه
- بهینه برای گرافهای وزن نامنفی؛ بهینگی مسیرهای محاسبه شده را اثبات میکند
- روی گرافهای جهتدار و بدون جهت کار میکند
- پایه و اساس برای تعداد بیشماری افزونه و الگوریتمهای مرتبط
کاربردها
- سیستمهای GPS و ناوبری: یافتن کوتاهترین مسیرها برای وسایل نقلیه و عابران پیاده
- پروتکلهای مسیریابی شبکه: تعیین مسیرهای بهینه برای بستههای داده در شبکههای کامپیوتری
- شبکههای اجتماعی: یافتن کوتاهترین مسیرهای اتصال بین کاربران یا تأثیرگذاران
- توسعه بازی: یافتن مسیر برای هوش مصنوعی و حرکت شخصیتهای غیرقابل بازی
- برنامهریزی حرکت ربات: محاسبه مسیرهای بهینه برای سیستمهای رباتیک
- مخابرات: بهینهسازی مسیریابی تماس و مسیرهای انتشار سیگنال
چگونه کار میکند
چگونه کار میکند
فاصله مبدأ را صفر و تمام فاصلههای دیگر را بینهایت تنظیم کنید. تمام رأسها را به عنوان بازدید نشده علامتگذاری کرده و یک صف اولویت ایجاد کنید.
رأس بازدید نشده با حداقل فاصله از مبدأ را با استفاده از صف اولویت انتخاب کنید.
برای هر همسایه رأس انتخاب شده، اگر مسیر از طریق رأس انتخاب شده فاصله کوتاهتری را ارائه میدهد، فاصله همسایه را بهروزرسانی کرده و آن را به صف اولویت اضافه کنید.
دامهای رایج
- استفاده از الگوریتم بر روی گرافهایی با وزنهای منفی، منجر به کوتاهترین مسیرهای نادرست میشود
- پیادهسازی ناکارآمد با عملیات استخراج-حداقل زمان خطی، منجر به عملکرد ضعیف میشود
- عدم بهروزرسانی صحیح فاصلهها هنگام بازدید مجدد همسایگان از طریق مسیرهای مختلف
پرسشهای متداول
چرا الگوریتم دایکسترا روی وزنهای منفی شکست میخورد؟
این الگوریتم فرض میکند که پس از نهایی شدن یک رأس، هیچ مسیر کوتاهتری از طریق رأسهای بازدید نشده یافت نمیشود. با وزنهای منفی، یک مسیر طولانیتر ممکن است بعداً با استفاده از یک یال منفی بهبود یابد و این فرض را نقض کند.
چه ساختار دادهای باید برای صف اولویت استفاده شود؟
هیپهای دودویی عملیات O(logV) را برای درج و استخراج فراهم میکنند که منجر به پیچیدگی کل O((V+E)logV) میشود. هیپهای فیبوناچی O(E+VlogV) را به دست میآورند اما ضرایب ثابت بزرگی دارند. آرایهها برای گرافهای کوچک مناسب هستند.
چگونه الگوریتم دایکسترا میتواند مسیر را به یک مقصد خاص پیدا کند؟
الگوریتم را به محض انتخاب رأس مقصد (نهایی شدن فاصله آن) خاتمه دهید و از محاسبات غیرضروری اجتناب کنید. به طور متناوب، مسیر را با حفظ اشارهگرهای والد در طول اجرا بازسازی کنید.
آیا میتوان از الگوریتم دایکسترا در گرافهای بدون جهت استفاده کرد؟
بله، گرافهای بدون جهت را میتوان به عنوان گرافهای جهتدار با یالهایی در هر دو جهت برای هر یال بدون جهت، که هر کدام وزن یکسانی دارند، نمایش داد. الگوریتم به طور یکسان بر روی نمایش دوطرفه کار میکند.
روشهای مرتبط
منابع
Dijkstra, E. W. (1959). A note on two problems in connexion with graphs. Numerische Mathematik, 1(1), 269-271.
باز کردن مرجع DOIکپی شد.Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press.
شابک: 978-0-262-03384-8کپی شد.