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

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

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

الگوریتم دیکسترا یکی از الگوریتم‌های پیمایش گراف است که مسئلهٔ کوتاه‌ترین مسیر از مبدأ واحد را برای گراف‌های وزن‌داری که یال با وزن منفی ندارند، حل می‌کند و در نهایت با ایجاد درخت کوتاه‌ترین مسیر، کوتاه‌ترین مسیر از مبدأ به همهٔ رأس‌های گراف را به دست می‌دهد.

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

شرح الگوریتم دیکسترا

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

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

برای دانلود سورس کد آماده الگوریتم دیکسترا محصول را خریداری کنید.

درباره محصول

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