آموزش الگوریتم دیکسترا کوتاهترین مسیر | توضیح گام به گام روند الگوریتم Dijkstra در ۱۰ مرحله

مقدمه الگوریتم دیکسترا کوتاهترین مسیر

الگوریتم دیکسترا (Dijkstra’s Algorithm) یا اولین الگوریتم کوتاهترین مسیر دیکسترا (Dijkstra’s Shortest Path First) از جمله الگوریتم‌هایی است که برای پیدا کردن کوتاهترین مسیر از گره آغازین تا گره هدف در گراف وزن دار (گرافی هست که یال‌های آن دارای وزن هستند) استفاده می‌شود.

الگوریتم دیکسترا یا دایجسترا (که البته درست آن دیکسترا هست ولی خوب دایجسترا هم بهش گفته می‌شود) الگوریتمی برای پیدا کردن کوتاهترین مسیر بین گره مبدا و دیگر گره ها در یک گراف است که البته از آن برای پیدا کردن کوتاهترین مسیر بین دو گره هم استفاده می‌شود. این الگوریتم اولین بار توسط یک دانشمند هلندی به نام ادسخر ویبه دیکسترا (Edsger Wybe Dijkstra) معرفی شد و بعد از حدوداً سه سال منتشر شد.

الگوریتم دیکسترا کوتاهترین مسیر، یک درخت از کوتاهترین مسیرها، که از رأس شروع شده تا نقاط دیگر گراف ادامه دارد، ایجاد می‌کند. تصور کنید در نقطه‌ای از شهر قرار دارید و یک قرار کاری بسیار مهم در نقطه دیگر شهر دارید و عجله می‌کنید که سر وقت به قرارتان برسید. حالا اگر برای یافتن مسیرهایی با کوتاهترین مسافت یا به عبارتی کمترین ترافیک روی نقشه بگردید به نحوی از الگوریتم دیکسترا استفاده کردید.

در این الگوریتم وزن‌های بر روی یال‌ها همان ترافیک خیابان یا مسافت طی شده برای گذر از آن خیابان را نشان می‌دهند. شکل زیر یک گراف را با تعدادی رأس و یال‌های وزن دار آن نشان می‌دهد.

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

• نظریه گراف — Graph Theory مطالب اساسی و انواع — کلیک کنید.
• انواع گراف — پاورپوینت آکادمیک — کلیک کنید.

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

روند کار این الگوریتم دارای چندین مرحله است:

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

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

در حین اجرای الگوریتم دیکسترا کوتاهترین مسیر، دو مورد نگهداری می‌شود. یکی مجموعه s از گره‌هایی که وزن کوتاهترین مسیر از مبدأ تا آنها مشخص‌شده و پیمایش شده‌اند و بعدی دنباله d که برای هر گره v بصورت dv که برای نشان دادن کوتاهترین مسیر از مبدأ تا گره v هست. به‌شرطی که تمام گره‌های این مسیر به‌جز خود گره v جزئی از مجموعه s باشند.یعنی قبلاً به دلیل کوتاهترین مسیر بودن پیمایش شده‌اند.

مقدار اولیه s تهی هست و مقدار d برای همه گره‌ها در ابتدا به‌جز آنهایی که مستقیماً به گره v (مبدأ) وصل هستند بی نهایت است. الگوریتم در هر مرحله گرهی را که خارج از مجموعه s هست و d آن به عبارتی وزن مسیر آن کمترین هست انتخاب کرده و داخل s قرار می‌دهد سپس مقادیر d را برای گره‌های همسایه بروز می‌کند چون پیمایش گره جدید مسیرهای جدیدی را تا مقصد برای گره مبدأ باز می‌کند.

ارائه درباره الگوریتم دایجسترا

کلیک کنید

مثالی از الگورریتم دیکسترا کوتاهترین مسیر

همان‌طور که در شکل ۱ مشاهده می‌کنید گره C گره مبدأ ما هست. در ابتدا گره‌هایی که مستقیماً با گره C در ارتباط هستند به‌عنوان مسیرهای احتمالی با خطوط خط‌چین قرمز مشخص شده‌اند. وزن‌های قرمز وزن مسیر طی شده از مبدأ تا گره مدنظر را نشان می‌دهد.

حالا بین سه مسیر اولی که داریم مسیر C-F با وزن ۱ کوتاه‌ترین مسیر موجود است پس پیمایش می‌شود. در شکل دو مشاهده می‌کنید که آن مسیر با خط چین زرد مشخص شده است و گره F گره پیمایش شده می باشد. وزن (C,1) نشان دهنده این است که گره F که پیمایش شده است گره ماقبل آن C بوده و با وزن ۱ پیمایش شده است.

در شکل ۳ مشاهده می‌کنیم که با پیمایش F مسیرهای جدیدی برای ما باز شدند. مسیرهای F-E و F-K در شکل ۲ وزن‌های نوشته شده روی گره‌های K و E بینهایت بود ولی در شکل ۳ به دلیل امکان پیمایش آن‌ها از طریق F دارای وزن هستند گره K دارای وزن ۵ به دلیل پیمایش از C تا F با وزن ۱ و جمع آن با وزن یال F تا K که ۴ است.

درنهایت با مجموع این دو یال وزن ۵ برای K نوشته شده است و همین‌طور برای E مجموع وزن‌های ۱+۷ در نظر گرفته شده است. در این مرحله از بین مسیرهای موجود که دوتاش از مرحله قبل داریم و دو تا هم جدیداً در شکل ۳ اضافه شده مسیری را انتخاب می‌کنیم که کوتاهترین باشد.

در ادامه الگوریتم دیکسترا کوتاهترین مسیر شکل ۴ نشان می‌دهد که C-A به دلیل داشتن کوتاهترین وزن با مقدار ۳ به‌عنوان مسیر بعدی انتخاب می‌شود. گره A وارد مجموعه گره‌های پیمایش شده همان مجموعه S که در بالا راجع به آن صحبت کردیم می‌شود.

اکنون با پیمایش گره A مسیرهای A-B و A-E به مسیرهای قابل پیمایش ما اضافه شدند. همچنین مسیر کوتاهتری به گره E داریم که قبلاً وزن آن ۸ بود ولی همان‌طور که در شکل ۵ مشاهده می‌کنید وزن آن به ۵ تغییر کرده است. اکنون از بین مسیرهای موجود مسیر A-B با وزن ۴ (۳+۱)انتخاب می‌شود.

اکنون گره B نیز پیمایش شد و مسیرهای جدید B-D و B-L (البته حواسمان هست که این مسیرها از مبدأ حساب می‌شوند به‌عنوان مثال منظور از B-D همان مسیر C-A-B-D هست). در شکل بعدی انتخاب گره بعدی را مشاهده می‌کنیم. همانطور که در شکل ۷ مشاهده می‌کنیم. مسیر C-A-B-D که اضافه‌شده وزن نوشته‌شده روی گره D را می‌تواند به ۹ تغییر دهد ولی ازآنجایی‌که وزن قبلی ۶ از آن کمتر هست دیگر ۹ را نمی‌نویسیم.

اکنون از بین گره‌های باقی‌مانده کوتاهترین مسیر مربوط به دو تا گره با وزن ۵ است گره‌های E و K، در این مواقع یکی را به دلخواه انتخاب می‌کنیم. گره E انتخاب شد ولی مسیر جدیدی اضافه نمی‌کند. در شکل ۷ از بین گره‌های باقی‌مانده گره K با کمترین وزن یعنی ۵ انتخاب می‌شود و امکان وجود دو مسیر C-F-K-D و مسیر C-F-K-L در شکل ۸ را فراهم می‌کند که مسیر C-F-K-L باعث می‌شود وزن گره K از ۸ به ۷ کاهش یابد. اکنون دو گره داریم با وزن‌های ۶ و ۷ خوب مشخص هست که گره D انتخاب می‌شود و مستقیم به گره مبدأ هم وصل هست. شکل ۹ را مشاهده کنید.

و در نهایت در شکل ۱۰ مشاهده می‌کنیم که گره L باقی‌مانده است و آن نیز به عنوان آخرین گره پیمایش می‌شود. این پیمایش از طریق گره F با وزن یالی ۷ (۵+۲) صورت می‌گیرد.

پیچیدگی زمانی الگوریتم دیکسترا کوتاهترین مسیر

در ساده‌ترین پیاده سازی الگوریتم دیکسترا کوتاهترین مسیر داده‌ها در آرایه‌ها یا بصورت لیست پیوندی ذخیره می‌شوند. درگراف بدون جهت هر یال دقیقا دو بار و در گراف جهت دار دقیقا یک بار پیمایش می‎شود در این حالت پیپچیدگی زمانی آن برابر خواهد بود با :

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

شبه کد الگوریتم دیکسترا کوتاهترین مسیر

algorithm: Dijkstra (G,S) 
 Input: G =(v,E) , S (the source node / vertex) 
 output: two sequence d and π 
 begin: for all vertexs w do  
          dw = ∞ 
          πw = NULL 
          ds = 0 
        while there is an unmarked vertex do 
          let w be an unmarked vertex such that dw is minimun 
          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= V.T تأثیر کاهش سرعت و افزایش مسافت یکسان خواهد بود. بنابراین می‌توان یکسری ضرایب تعدیلی در فواصل بین نقاط ضرب کرد و بدین گونه در محاسبات لحاظ کرد. از جمله مهم‌ترین این ضرایب می‌توان به ۱- ضریب ترافیک و شلوغی ۲- ضریب عرض معبر ۳- ضریب شیب که نشانگر افت سرعت در سربالایی ها است اشاره کرد.

اگرچه تعیین این ضرایب نیاز به افراد متخصص در زمینه ترافیک و.. دارد ولی می‌توان انتظار داشت که در بیشتر مواقع این ضرایب بین ۱ تا ۲ بسته به شرایط تغییر کنند.

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

کلیک کنید

سخن آخر در مورد الگوریتم دیکسترا کوتاهترین مسیر

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

همچنین در این مقاله مراحل این الگوریتم به‌صورت گام‌به‌گام همراه با رسم شکل و توضیحات لازم بیان‌ شده است. امیدوارم از مطالعه این مقاله لذت برده باشید و برایتان کاربردی بوده باشد.