Dijkstra Algorithm

الگوریتم دایسترا یکی از معروف‌ترین و مهم‌ترین الگوریتم‌های جستجوی مسیر در علم کامپیوتر است که برای پیدا کردن کوتاه‌ترین مسیر در گراف‌های وزندار (گراف‌هایی که بر روی یال‌های خود وزن دارند) استفاده می‌شود. این الگوریتم در سال 1956 توسط ادسگار دایسترا، ریاضیدان و دانشمند علوم کامپیوتر هلندی، معرفی شد.

بیوگرافی ادسگار دایسترا:

ادسگار دایسترا (Edsger Dijkstra) یکی از بزرگ‌ترین چهره‌های علم کامپیوتر در قرن 20 بود که تأثیرات عمیقی در نظریه الگوریتم‌ها و برنامه‌نویسی داشت . یکی از مهم‌ترین دستاوردهای او، الگوریتم دایسترا است که تا امروز در بسیاری از سیستم‌های مسیریابی و شبکه‌ها استفاده می‌شود.

الگوریتم دایسترا: چطور ساخته شد؟

الگوریتم دایسترا به‌طور خاص برای حل مسائل کوتاه‌ترین مسیر در گراف‌ها طراحی شد. فرض کنید که یک نقشه جاده‌ای دارید که در آن، هر جاده دارای یک وزن (مثل زمان سفر یا فاصله) است. شما می‌خواهید از یک نقطه شروع به نقطه‌ای دیگر بروید و به دنبال پیدا کردن کم‌هزینه‌ترین مسیر هستید.

الگوریتم دایسترا به این صورت کار می‌کند که از نقطه شروع آغاز کرده و به‌طور تدریجی نزدیک‌ترین گره‌ها را بررسی می‌کند و مسیرهای کوتاه‌تر را اولویت می‌دهد. این کار را تا زمانی ادامه می‌دهد که به مقصد برسد یا تمام مسیرها بررسی شوند. به این ترتیب، دایسترا از تمام مسیرهای ممکن عبور می‌کند و به طور بهینه‌ترین مسیر را پیدا می‌کند.

1. الگوریتم از یک گره شروع می‌کند و هزینه‌ی رسیدن به آن گره را صفر در نظر می‌گیرد.

2. سپس تمام گره‌های مجاور به این گره را بررسی می‌کند و هزینه رسیدن به آن‌ها را محاسبه می‌کند.

3. گره‌ای که کمترین هزینه را داشته باشد، انتخاب شده و بررسی‌ها ادامه پیدا می‌کنند.

4. این فرایند ادامه می‌یابد تا الگوریتم به مقصد برسد یا تمام گره‌ها را بررسی کند.

نقاط ضعف این الگوریتم:

1. برای گراف‌های با وزن‌های غیرمنفی مناسب است، زیرا فرض می‌کند که هزینه‌ها همیشه مثبت هستند و در نتیجه از بازگشت به گره‌های قبلی که هزینه کمتری دارند جلوگیری می‌شود.

2.در حالی که الگوریتم دایسترا به دلیل سادگی و دقت در یافتن کوتاه‌ترین مسیر بسیار محبوب است، یکی ازمحدودیت‌های آن این است که تمامی مسیرها را بررسی می‌کند و در نتیجه ممکن است برای مسیریابی‌های پیچیده‌تر یا شبکه‌های بزرگ زمان‌بر باشد.

برای حل این مشکل، الگوریتم *A در دهه 1970 معرفی شد. A* (A-star) یک بهبود بر روی دایسترا است که از یک تابع هزینه تخمینی (Heuristic) استفاده می‌کند. این تابع به الگوریتم کمک می‌کند که مسیرهای احتمالاً بهینه را زودتر از سایر مسیرها بررسی کند، و در نتیجه زمان اجرای آن سریع‌تر از دایسترا خواهد بود.

بگذارید فرق اصلی *A و Dijkstra رو بررسی کنیم:

فرض کنید میخواهید با استفاده از الگوریتم Dijkstra مسیر خودتون رو پیدا کنید ولی این بار به جای اینکه فقط مسیرهای موجود رو بررسی کنید، می‌دونید که مقصد شما در یک جهت خاص از نقشه قرار داره. الگوریتم *A دقیقا مثل این می‌مونه که شما با داشتن یه نقشه و دیدن مقصد در دوردست، به مسیرهایی توجه می‌کنید که مستقیم‌تر و سریع‌تر به مقصد می‌رسند. این الگوریتم علاوه بر اینکه مسیرهای کوتاه‌تر رو بررسی می‌کنه، از یک راهنمای هوشمند استفاده می‌کنه (که بهش هزینه تخمینی می‌گن) تا سریع‌تر به مقصد برسید و مسیرهای نامناسب رو کنار بذارید. به این ترتیب، برخلاف Dijkstra که تمام مسیرها رو بررسی می‌کنه، *A فقط مسیرهایی رو بررسی می‌کنه که به نظر میاد سریع‌تر شما رو به مقصد می‌رسونند.

افزودن تابع تخمینی به الگوریتم دایسترا، عملاً باعث شد که *A به یک ابزار محبوب برای مسیریابی در نقشه‌ها، بازی‌های ویدیویی و سیستم‌های مسیریابی پیچیده تبدیل شود.