پیاده‌سازی الگوریتم Dijkstra جهت یافتن مسیر بهینه مابین رئوس گراف در پایتون

در مقالۀ Graph چیست و این دیتا استراکچر چه کاربردهایی دارا است؟ به بررسی دیتا استراکچر گراف پرداخته و با کاربردهای آن آشنا شدیم و گفتیم که یکی از کاربردهایش مدل‌سازی نقشۀ راه‌های بین‌شهری است که در آن هر یک از شهرها به عنوان رئوس گراف و جاده‌های مابین آن‌ها نیز به عنوان یال‌های گراف در نظر گرفته می‌شوند.

حال در این آموزش قصد داریم تا به معرفی یکی از الگوریتم‌های کاربردی تحت عنوان Dijkstra به منظور اِعمال روی گراف‌هایی بپردازیم که با به‌کارگیری آن‌ها می‌توان کمترین هزینه مابین دو رأس از گراف مربوطه را به دست آورد. در واقع، واژۀ «هزینه» در این الگوریتم معانی متفاوت می‌تواند داشته باشد که از آن جمله می‌توان به کوتاه‌ترین مسیر مابین نقشۀ جاده‌های بین‌شهری و شبکه‌های تلفنی به منظور هدایت تماس‌ها به خطوطی با پهنای‌باند بالا و مواردی از این دست اشاره کرد به طوری که هدف این الگوریتم جستجو در گراف مدل‌سازی شده و پیدا کردن بهینه‌ترین مسیر مابین رئوس مد نظر می‌باشد.

اکنون به منظور درک بهتر مفهوم کوتاه‌ترین مسیر در گراف مربوط به نقشۀ جاده‌های بین‌شهری سناریویی را در نظر می‌گیریم که در آن قصد داریم تا روشی را به منظور پیدا کردن کوتاه‌ترین مسیر مابین دو نقطه از نقشۀ مثال فوق پیاده‌سازی کنیم به طوری که کاربر دو نقطۀ مبدأ و مقصد مورد نظر خود از گراف را وارد کرده و الگوریتم پیاده‌سازی‌شده کوتاه‌ترین فاصلۀ مابین آن‌ها را روی نقشه به وی پیشنهاد می‌دهد. به طور مثال، فرض کنید قصد داریم تا از شهر بوشهر به گرگان مسافرت کنیم که با پیاده‌سازی الگوریتم مربوطه، کوتاه‌ترین فاصلۀ مابین این دو شهر را یافته و مسیر پیشنهادی را انتخاب می‌کنیم.

در واقع، الگوریتم Dijkstra وظیفۀ پیدا کردن کوتاه‌ترین مسیر مابین دو رأس از یک گراف وزن‌دار را دارا است که در ادامه مراحل کار آن را گام‌به‌گام تشریح می‌کنیم اما پیش از ادامۀ بحث بهتر است بدین سؤال پاسخ دهیم که «الگوریتم چیست و چه کاربردهایی دارا است؟». به طور کلی، الگوریتم‌ روشی جهت حل مسائل است و در توسعۀ نرم‌افزار نیز به مراحل گام‌به‌گامی گفته می‌شود که به منظور انجام عملیات مد نظر در راستای پیاده‌سازی، توسعه و تشریح چگونگی عملکرد اپلیکیشن طراحی می‌شوند (جهت کسب اطلاعات بیشتر در رابطه با مفهوم الگوریتم به آموزش الگوریتم چیست؟ مراجعه کنید.)

آشنایی با نحوۀ کار الگوریتم Dijkstra

ابتدا به ساکن نحوۀ عملکرد الگوریتم دایجکسترا را گام‌به‌گام تشریح می‌کنیم تا ببینیم که چگونه می‌توان با به‌کارگیری این الگوریتم مسیری با کمترین هزینه مابین دو رأس گراف را تشخیص داد:

1. ابتدا هزینۀ پیمایش برای رأس مبدأ را برابر با صفر قرار می‌دهیم که این مسئله کاملاً بدیهی است چرا که هزینه‌ای صرف انتقال به خود رأس نمی‌شود.

2. رأس مبدأ را به عنوان رأس اصطلاحاً Visited یا پیمایش‌شده در نظر می‌گیریم.

3. حال برای محاسبۀ هزینۀ پیمایش از رأس مبدأ به هر یک از رئوس همسایۀ آن کافی است تا هزینۀ خود رأس (صفر) را با وزن هر یک از یال‌های مابین رئوس همسایۀ رأس مبدأ جمع کنیم.

4. از میان رئوسی که هزینۀ انتقال آن‌ها محاسبه شده است، رأسی با کمترین هزینه را انتخاب کرده و به عنوان رأس بعدی برای پیمایش در نظر می‌گیریم.

5. اکنون رأسی با کمترین هزینه که در مرحلۀ پیشین مشخص شده است را به عنوان رأس جاری در نظر گرفته و در ادامه باید هزینۀ پیمایش به رئوس همسایۀ آن را محاسبه کنیم.

6. در این مرحله به منظور محاسبۀ هزینۀ پیمایش رئوس همسایه کافی است تا وزن یال مابین رأس کنونی و رأس مد نظر را با هزینۀ انتقال به رأس کنونی جمع کنیم.

7. حال بررسی می‌کنیم ببینیم چنانچه از میان رئوس همسایه رأسی داشته باشیم که هزینۀ انتقال به آن را در مراحل پیشین محاسبه کرده‌ایم و این مقدار بزرگ‌تر از هزینه‌ای است که در گام ششم برای رأس مذکور محاسبه شده، مقدار جدید را جایگزین مقدار مربوط به هزینۀ پیشین می‌کنیم.

8. مجدداً از میان تمامی رئوسی که هزینۀ انتقال برای آن‌ها محاسبه شده است، رأسی با کمترین هزینه را انتخاب کرده و به عنوان رأس کنونی در نظر می‌گیریم.

9. مراحل فوق را تا جایی ادامه می‌دهیم که به رأس مقصدی برسیم که توسط کاربر تعریف شده است.

جمع‌بندی
در این مقاله به بررسی الگوریتم‌ پرکاربردی تحت عنوان Dijkstra به منظور اِعمال روی دیتا استراکچر گراف پرداختیم و دیدیم که الگوریتم مذکور را می‌توان جهت تشخیص مسیری بهینه در رابطه با تمامی مسائلی به کار برد که قابلیت مدل‌سازی با استفاده از دیتا استراکچر گراف را دارند. در پایان، اگر علاقه‌مند به فراگیری زبان برنامه‌نویسی پایتون هستید، توصیه می‌کنیم به دورۀ آموزش پایتون در سکان آکادمی مراجعه نمایید.