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

در این پست سورس کد الگوریتم دیکسترا Dijkstra در متلب را آماده کرده‌ایم. با استناد به ویکی پدیا الگوریتم دیکسترا یا الگوریتم دَیکسترا (دایجسترا)  توسط دانشمند هلندی، اِدْسْخِر دَیْکْسْترا در سال ۱۹۵۹ ارایه شد. الگوریتم دیکسترا یکی از الگوریتم‌های پیمایش گراف است که مسئلهٔ کوتاه‌ترین مسیر از مبدأ واحد را برای گراف‌های وزن‌داری که یال با وزن منفی ندارند، حل می‌کند و در نهایت با ایجاد درخت کوتاه‌ترین مسیر، کوتاه‌ترین مسیر از مبدأ به همهٔ رأس‌های گراف را به دست می‌دهد.

در نظریه گراف‌ها مسئلهٔ یافتن کوتاه‌ترین مسیر در واقع مسئلهٔ یافتن مسیری بین دو رأس (یا گره) است به گونه‌ای که مجموع وزن یال‌های تشکیل دهندهٔ آن کمینه شود. برای مثال می‌توان مسئلهٔ یافتن سریع‌ترین راه برای رفتن از یک مکان به مکان دیگر روی نقشه را، در نظر گرفت؛ در این حالت رأس‌ها نشان دهندهٔ مکان‌ها و یال‌ها نشان دهندهٔ بخش‌های مسیر هستند که برحسب زمانِ لازم برای طی کردن آن‌ها وزن گذاری شده‌اند.

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

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

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

درباره محصول

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