Grafų teorijoje trumpiausio kelio problema yra radimas kelio tarp dviejų svorinio grafo viršūnių, kad briaunų svorių suma būtų mažiausia.

Problema beieškant trumpiausio kelio tarp dviejų apmokestintų kelių sankirtos, kurių apmokestinimas neturi įtakos nuvažiuotam atstumui, gali būti suvesta į klasikinę trumpiausio kelio problemą, kuri vaizduoja susikirtimus panaudojant papildomas viršūnes ir kraštines. Klasikinė trumpiausio kelio problema gali būti išspręsta naudojantis Dijkstros algoritmu.

https://lt.wikipedia.org/wiki/Dijkstros_algoritmas

Paveiksle pažymėtas pigiausias maršrutas:

Norint įrodyti, kad šis maršrutas yra optimaliausias, būtina palyginti visus galimus variantus.

Tačiau galima peržvelgti kelius ir įsitikinti, kad reikia vengti brangių kelių: kelio iš B į Mugą, taip pat kelio iš A į F ir iš B į F.

Pažymėkime sankirtas

Peržvelgiame maršrutus ir telieka patikrinti du maršrutus