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

در نظریه گرافها مسئلهٔ یافتن کوتاه ترین مسیر در واقع مسئلهٔ یافتن مسیری بین دو رأس ( یا گره ) است به گونه ای که مجموع وزن یال های تشکیل دهندهٔ آن کمینه شود. برای مثال می توان مسئلهٔ یافتن سریع ترین راه برای رفتن از یک مکان به مکان دیگر روی نقشه را، در نظر گرفت؛ در این حالت رأس ها نشان دهندهٔ مکان ها و یال ها نشان دهندهٔ بخش های مسیر هستند که برحسب زمانِ لازم برای طی کردن آن ها وزن گذاری شده اند.
اگر یک گراف وزن دار ( که شامل مجموعهٔ V از رئوس، مجموعهٔ E از یال ها و تابع وزن f  : E  →  R است ) و یک عنصر مانند v از مجموعهٔ V داشته باشیم، هدف ما یافتن مسیری مانند P از v به 'v است به گونه ای که:
کوتاه ترین مسیر بین تمام مسیرهای موجود از v به 'v باشد.
این مسئله گاهی تحت عنوان مسئلهٔ یافتن کوتاهترین مسیر بین دو راس نام گذاری می شود تا از سایر حالت های کلی که به شرح زیر هستند، متمایز شود:
• مسئلهٔ یافتن کوتاه ترین مسیر از مبدا واحد که در آن هدف یافتن کوتاه ترین مسیر از رأس مبدا v تا تمامی رئوس دیگر در گراف است.
• مسئلهٔ یافتن کوتاه ترین مسیر به مقصد واحد که در آن هدف یافتن کوتاه ترین مسیر از تمامی رئوس گراف تا رأس مقصد v است.
• مسئلهٔ یافتن کوتاه ترین مسیر بین هر دو رأس که در آن هدف یافتن کوتاه ترین مسیر بین هر جفت رأسِ v و 'v در گراف است.
این حالت های عمومی به صورت معناداری از الگوریتم های کارآمدتری نسبت به مسئلهٔ مورد نظر ما برخوردارند.
مهم ترین الگوریتم ها برای حل این مسئله عبارتند از:
• الگوریتم دیکسترا: مسئلهٔ یافتن کوتاه ترین مسیر بین دو رأس، از مبدأ واحد و به مقصد واحد را حل می کند.
• الگوریتم بلمن - فورد: مسئلهٔ یافتن کوتاه ترین مسیر از مبدأ واحد را در حالتی حل می کند که وزن یال ها منفی نیز می تواند باشد.
• الگوریتم جستجوی آ*: با کمک روش های ابتکاریِ جستجو، مسئلهٔ یافتن کوتاه ترین مسیر بین دو رأس را تسریع می بخشد.
• الگوریتم فلوید - وارشال: مسئلهٔ یافتن کوتاه ترین مسیر بین هر دو رأس را حل می کند.
• الگوریتم جانسون: که مسئلهٔ یافتن کوتاه ترین مسیر بین هر دو رأس را حل می کند و در گراف های پراکنده ممکن است سریع تر از فلوید - وارشال عمل کند.
• نظریهٔ بی نظمی ها: ( در بدترین حالت ) کوتاه ترین مسیر محلی را می یابد.