الگوریتم دایجسترا (Dijkstra) – از صفر تا صد

«الگوریتم دایجسترا» (Dijkstra's Algorithm) یا «اولین الگوریتم کوتاه‌ترین مسیر دایجسترا» (Dijkstra's Shortest Path First Algorithm | SPF) (البته تلفظ صحیح این نام، الگوریتم دیکسترا است که به صورت متداول به آن دایجسترا گفته می‌شود)، الگوریتمی است که برای پیدا کردن کوتاه‌ترین مسیر بین دو «گره» (Node | راس) در گراف به کار می‌رود. این گراف، ممکن است نشان‌گر شبکه جاده‌ها یا موارد دیگری باشد. الگوریتم دایجسترا در سال ۱۹۵۶، توسط دانشمند کامپیوتری با نام «ادسخر ویبه دیکسترا» (Edsger Wybe Dijkstra) مطرح و سه سال بعد، منتشر شد. الگوریتم دایجسترا دارای انواع گوناگونی است. الگوریتم اصلی، کوتاه‌ترین مسیر بین دو گره را پیدا می‌کند؛ اما نوع متداول‌تر این الگوریتم، یک گره یکتا را به عنوان گره مبدا (آغازین) در نظر می‌گیرد و کوتاه‌ترین مسیر از مبدا به دیگر گره‌ها در گراف را با ساختن درخت کوتاه‌ترین مسیر پیدا می‌کند.

برای یک گره مبدا داده شده، الگوریتم، کوتاه‌ترین مسیر بین آن گره و دیگر گره‌ها را پیدا می‌کند. همچنین، الگوریتم دایجسترا برای پیدا کردن کوتاه‌ترین مسیر از یک گره یکتا به گره مقصد یکتای دیگری به کار می‌رود؛ برای انجام این کار، الگوریتم هنگامی که کوتاه‌ترین مسیر از مبدا به مقصد را پیدا کند، متوقف می‌شود. برای مثال، اگر گره‌های گراف نشان‌گر شهرها و یال‌ها هزینه سفر بین شهرهایی باشند که با جاده‌های مستقیم به هم متصل شده‌اند، از الگوریتم دایجسترا می‌توان برای پیدا کردن کوتاه‌ترین راه بین یک شهر و همه شهرهای دیگر استفاده کرد. یکی از کاربردهای اصلی الگوریتم دایجسترا، پروتکل‌های مسیریابی شبکه است که از جمله آن‌ها می‌توان به IS-IS (سیستم میانی به سیستم میانی | Intermediate System to Intermediate System) و «ابتدا کوتاه‌ترین مسیر باز» (Open Shortest Path First | OSPF) اشاره کرد.

از الگوریتم دایجسترا، به عنوان یک زیر روال نیز در برخی از دیگر الگوریتم‌ها مانند «الگوریتم جانسون» (Johnson's Algorithm) استفاده می‌شود. الگوریتم دایجسترا از برچسب‌هایی استفاده می‌کند که اعداد صحیح یا حقیقی مثبت هستند. جالب توجه است که الگوریتم دایجسترا می‌تواند برای استفاده از برچسب‌های تعریف شده به هر شکلی، تعمیم پیدا کند. چنین تعمیمی، «تعمیم الگوریتم کوتاه‌ترین مسیر دایجسترا» نامیده می‌شود.

الگوریتم دایجسترا (Dijkstra) برای یافتن کوتاه‌ترین مسیر

فرض می‌شود که یک گراف به همراه یک راس مبدا داده شده و هدف پیدا کردن کوتاه‌ترین مسیر به همه راس‌های موجود در گراف مذکور است. الگوریتم دایجسترا شباهت زیادی به «الگوریتم پریم» (Prim’s Algorithm) برای «درخت پوشای کمینه» (Minimum Spanning Tree) دارد. در الگوریتم دایجسترا نیز درخت کوتاه‌ترین مسیر با استفاده از مبدا داده شده به عنوان ریشه، ساخته می‌شود.

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

1. ساخت مجموعه sptSet (مجموعه درخت کوتاه‌ترین مسیر | Shortest Path Tree Set) که به دنبال راس‌های قرار گرفته در درخت کوتاه‌ترین مسیر می‌گردد؛ یعنی، راسی که حداقل فاصله آن از مبدا محاسبه و نهایی شده است. به طور مقدماتی، این مجموعه خالی است.
2. تخصیص یک مقدار فاصله به همه راس‌ها در گراف ورودی. مقداردهی اولیه همه مقادیر فاصله‌ها به عنوان INFINITE. تخصیص مقدار فاصله صفر به راس مبدا که موجب می‌شود این راس در ابتدا انتخاب شود.
3. تا هنگامی که sptSet شامل همه راس‌ها نشده است، اقدامات زیر انجام می‌شود:
   • راس u انتخاب می‌شود که در sptSet نیست و دارای حداقل مقدار فاصله است.
   • u در sptSet قرار می‌گیرد.
   • مقدار فاصله از همه راس‌های مجاور u به روز رسانی می‌شود. برای به روز رسانی مقادیر فاصله، در همه راس‌های مجاور تکرار انجام می‌شود. برای هر راس مجاور v، اگر مجموع فاصله u (از کد منبع) و وزن یال u-v کمتر از مقدار فاصله v باشد، مقدار فاصله از v به روز رسانی می‌شود.

برای درک بهتر موضوع، مثال زیر مورد بررسی قرار خواهد گرفت.

مجموعه sptSet در ابتدا خالی است و فاصله تخصیص پیدا کرده به راس‌ها برابر با { INF, INF, INF, INF, INF, INF, INF ,صفر} هستند که در آن INF نشان‌گر بی‌نهایت (Infinite) است. اکنون، باید راسی که دارای کم‌ترین مقدار فاصله است انتخاب شود. راس ۰ انتخاب می‌شود و در sptSet قرار می‌گیرد. بنابراین، sptSet به صورت {0} می‌شود. پس از قرار دادن ۰ در sptSet، مقدار فاصله‌ها از راس‌های مجاور آن به روز رسانی می‌شوند. راس‌های مجاور ۰، راس‌های ۱ و ۷ هستند. مقدار فاصله برای ۱ و ۷، برابر با ۴ و ۸ است. زیرگراف زیر، راس‌ها و مقدار فاصله آن‌ها را نشان می‌دهد. در این گراف، تنها راس‌هایی با مقدار فاصله متناهی نشان داده شده‌اند. راس‌های موجود در SPT به رنگ سبز نمایش داده شده‌اند.

راسی که حداقل فاصله را از مبدا دارد و تاکنون انتخاب نشده است، یعنی در sptSET قرار ندارد، انتخاب می‌شود. راس ۱ انتخاب و به sptSet اضافه می‌شود. بنابراین، اکنون sptSet به صورت {۱ ,۰} خواهد بود. مقدار فاصله راس‌های مجاور ۱ به روز رسانی می‌شود. مقدار فاصله از راس ۲ برابر با ۱۲ خواهد بود.

راسی با کمترین مقدار فاصله که در حال حاضر در SPT قرار ندارد باید انتخاب شود. راس ۷ انتخاب می‌شود. بنابراین، sptSet اکنون به صورت {۷ , 1 , ۰} خواهد بود. مقدار فاصله از راس‌های مجاور ۷ محاسبه می‌شود. مقدار فاصله از راس ۶ و ۸ متناهی است (به ترتیب، ۱۵ و ۹).

راسی با حداقل مقدار فاصله که در SPT نیز قرار ندارد باید انتخاب شود. راس ۶ انتخاب می‌شود. بنابراین، sptSet اکنون برابر با {۶ ,۷ ,۱ ,۰} است. مقدار فاصله‌ها از راس‌های مجاور ۶ باید به روز رسانی شود. مقدار فاصله برای راس‌های ۵ و ۸ به روز رسانی می‌شود.

مراحل بیان شده تا جایی تکرار می‌شوند که sptSet شامل همه راس‌های گراف داده شده نباشد. در نهایت، درخت کوتاه‌ترین مسیر (SPT) زیر حاصل می‌شود.

برای پیاده‌سازی الگوریتم بالا، از آرایه بولین []sptSet برای ارائه مجموعه‌ای از راس‌های قرار گرفته در SPT استفاده می‌شود. اگر مقدار [sptSet[v «درست» (True) باشد، راس v در SPT قرار می‌گیرد، در غیر این صورت، یعنی اگر [sptSet[v «غلط» (False) باشد، راس v در SPT قرار نمی‌گیرد. آرایه []dist برای ذخیره‌سازی کوتاه‌ترین مقدار فاصله از همه راس‌ها مورد استفاده قرار می‌گیرد.

کد الگوریتم دایجسترا در ++C

فیلم آموزش ساختمان داده ها و پیاده سازی در سی پلاس پلاس C++‎ در فرادرس

کلیک کنید

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

فیلم آموزش الگوریتم ها و روش های جست و جو در آرایه (رایگان) در فرادرس

کلیک کنید

کد الگوریتم دایجسترا در #C

فیلم آموزش طراحی الگوریتم + حل مثال های عملی در فرادرس

کلیک کنید

کد الگوریتم دایجسترا در پایتون

فیلم مجموعه آموزش ساختمان داده و طراحی الگوریتم – از دروس دانشگاهی تا کاربردی در فرادرس

کلیک کنید

اگر نوشته بالا برای شما مفید بوده است، آموزش‌های زیر نیز به شما پیشنهاد می‌شوند:

• مجموعه آموزش‌‌های برنامه‌‌‌نویسی
• آموزش ساختمان داده‌ها
• مجموعه آموزش‌های ساختمان داده و طراحی الگوریتم
• معرفی منابع آموزش ویدئویی هوش مصنوعی به زبان فارسی و انگلیسی
• زبان برنامه‌نویسی پایتون (Python) — از صفر تا صد
• آموزش ساختمان داده — مجموعه مقالات جامع وبلاگ فرادرس

^^