Masalah lintasan terpendek

Dalam teori graf, masalah lintasan terpendek merupakan masalah yang menanyakan bagaimana mencari sebuah jalur pada graf yang meminimalkan jumlah bobot sisi pembentuk jalur tersebut, jika diberikan sebuah graf berbobot. Masalah dari mencari jarak terpendek antara dua persimpangan dari peta jalan dapat dimodelkan dari kasus spesial dari masalah jarak terpendek dalam graf.