الگوریتم دیکسترا (Dijkstra's Algorithm)، در ریاضیات (Mathematics)
انواع روش های بهینه سازی (Optimization Methods) را در آموزش زیر شرح دادیم :
الگوریتم دیکسترا (Dijkstra's Algorithm) :
📌 معرفی
الگوریتم دیکسترا (Dijkstra's Algorithm) توسط ادسخر دیکسترا در سال ۱۹۵۶ ارائه شد. این الگوریتم برای یافتن کوتاه ترین مسیر از یک گره مبدأ به تمام گره های دیگر در یک گراف با وزن های غیرمنفی استفاده می شود. این الگوریتم یک الگوریتم حریصانه (Greedy) است و پایه بسیاری از الگوریتم های مسیریابی دیگر است.
📐 مراحل الگوریتم
مقادیر فاصله از مبدأ به همه گره ها را بینهایت در نظر بگیر، به جز خود مبدأ که فاصله آن صفر است.
مجموعه ای از گره های بازدید نشده ایجاد کن.
تا زمانی که گره های بازدید نشده باقی مانده اند:
گره بازدید نشده با کوچکترین فاصله فعلی را انتخاب کن (این گره "جاری" می شود).
برای هر همسایه بازدید نشده این گره، فاصله جدید = فاصله گره جاری + وزن یال را محاسبه کن. اگر این فاصله جدید از فاصله فعلی همسایه کمتر بود، آن را به روز کن.
گره جاری را به عنوان بازدید شده علامت بزن.
🔧 پیچیدگی
با استفاده از آرایه ساده:
\[ O(V^2) \]که V تعداد گره ها است.
با استفاده از هیپ (Heap) برای انتخاب گره با کمترین فاصله:
\[ O((V+E) \log V) \]که E تعداد یال ها است.
