مسئله یافتن کوتاهترین مسیر

گرافی با ۶ راس و ۷ یال
در نظریه گرافها مسئله یافتن کوتاه‌ترین مسیر در واقع مسئله یافتن مسیری بین دو راس (یا گره) است به گونه‌ای که مجموع وزن یال‌های تشکیل دهنده آن کمینه شود. برای مثال می‌توان مسئله یافتن سریع‌ترین راه برای رفتن از یک مکان به مکان دیگر روی نقشه را، در نظر گرفت؛ در این حالت راس‌ها نشان دهنده مکان‌ها و یال‌ها نشان دهنده بخش‌های مسیر هستند که برحسب زمان لازم برای طی کردن آن‌ها وزن گذاری شده‌اند.
اگر یک گراف وزن دار (که شامل مجموعه V از رئوس، مجموعه E از یال‌ها و تابع وزن f : E → R است) و یک عنصر مانند v از مجموعه V داشته باشیم، هدف ما یافتن مسیری مانند P از v به v است به گونه‌ای که:
کوتاه‌ترین مسیر بین تمام مسیرهای موجود از v به v باشد.
این مسئله گاهی تحت عنوان مسئله یافتن کوتاهترین مسیر بین دو راس نام گذاری می‌شود تا از سایر حالت‌های کلی که به شرح زیر هستند، متمایز شود:
مسئله یافتن کوتاه‌ترین مسیر از مبدا واحد که در آن هدف یافتن کوتاه‌ترین مسیر از راس مبدا v تا تمامی رئوس دیگر در گراف است.
مسئله یافتن کوتاه‌ترین مسیر به مقصد واحد که در آن هدف یافتن کوتاه‌ترین مسیر از تمامی رئوس گراف تا راس مقصد v است.
مسئله یافتن کوتاه‌ترین مسیر بین هر دو راس که در آن هدف یافتن کوتاه‌ترین مسیر بین هر جفت راس v و v در گراف است.
این حالت‌های عمومی به صورت معناداری از الگوریتم‌های کارآمدتری نسبت به مسئله مورد نظر ما برخوردارند.
الگوریتم‌ها
مهم‌ترین الگوریتم‌ها برای حل این مسئله عبارتند از:
الگوریتم دیکسترا: مسئله یافتن کوتاه‌ترین مسیر بین دو راس، از مبدا واحد و به مقصد واحد را حل می‌کند.
الگوریتم بلمن-فورد: مسئله یافتن کوتاه‌ترین مسیر از مبدا واحد را در حالتی حل می‌کند که وزن یال‌ها منفی نیز می‌تواند باشد.
الگوریتم جستجوی آ*: با کمک روش‌های ابتکاری جستجو، مسئله یافتن کوتاه‌ترین مسیر بین دو راس را تسریع می‌بخشد.
الگوریتم فلوید-وارشال: مسئله یافتن کوتاه‌ترین مسیر بین هر دو راس را حل می‌کند.
الگوریتم جانسون: که مسئله یافتن کوتاه‌ترین مسیر بین هر دو راس را حل می‌کند و در گراف‌های پراکنده ممکن است سریع‌تر از فلوید-وارشال عمل کند.
نظریه بی‌نظمی‌ها: (در بدترین حالت) کوتاه‌ترین مسیر محلی را می‌یابد.
کاربردها
مسئله یافتن کوتاه‌ترین مسیر برای یافتن مسیرهای میان مکان‌های واقعی از قبیل راه‌های عبور و مرور در نقشه‌های اینترنتی مانند نقشه گوگل استفاده می‌شود.
اگر یک ماشین مجازی غیرواقعی را به صورت گرافی در نظر بگیریم که در آن راس‌ها بیان کننده حالت‌ها و یال‌ها بیان کننده گذار از حالتی به حالتی دیگر باشند، می‌توان از الگوریتم یافتن کوتاه‌ترین مسیر به عنوان ابزاری برای یافتن دنباله‌ای بهینه از انتخاب‌ها به منظور رسیدن به یک حالت ویژه استفاده کرد. هم چنین می‌توان این الگوریتم را به منظور دست یابی به یک کران پایین از زمان مورد نیاز برای رسیدن به یک حالت مشخص به کار برد. برای مثال اگر راس‌ها بیانگر حالت‌های یک پازل مانند مکعب رابیک و هر یک از یال‌های جهت دار بیانگر یک حرکت یا چرخش باشند، می‌توان از الگوریتم‌های کوتاه‌ترین مسیر بهره برد به گونه‌ای که این الگوریتم‌ها به راه حلی با کمترین تعداد حرکت منجر شوند.
گاهی در ساختار شبکه‌های ارتباطی یا شبکه‌های مخابراتی از این مسئله با عنوان مسئله یافتن کم تاخیرترین مسیر یاد می‌کنند که اغلب ارتباط تنگاتنگی با مسئله یافتن عریض‌ترین مسیر دارد.
این مسئله در رباتیک، حمل و نقل و طراحی مدارهای VLSI نیز کاربرد دارد.
مسائل مرتبط
برای مشاهده مسئله یافتن کوتاه‌ترین مسیر در هندسه محاسباتی به کوتاه‌ترین مسیر اقلیدسی مراجعه نمایید.
مسئله فروشنده دوره گرد برای یافتن کوتاه‌ترین مسیری است که از هر یک از رئوس دقیقا یک بار بگذرد و به مبدا بازگردد. برخلاف مسئلهی یافتن کوتاه‌ترین مسیر که برای گراف‌های فاقد دور منفی در زمان چند جمله‌ای قابل است، این مسئله از دسته مسائل ان پی-کامل است. مسئله یافتن طولانی‌ترین مسیر در یک گراف نیز از جمله مسائل ان پی-کامل است.
مسئله مسافر کانادایی و مسئله یافتن کوتاه‌ترین مسیر اتفاقی حالت‌های عمومی هستند که در آن‌ها یا گراف به طور کامل برای مسافر مشخص نیست یا گراف با زمان تغییر می‌کند یا پیمایش‌ها احتمالی هستند.
اگر در گراف تغییر شکلی (از قبیل کاهش تعداد گره‌ها) رخ دهد، نیازمند محاسبه مجدد کوتاه‌ترین مسیر خواهیم بود.
درخت کوتاه‌ترین مسیر