Trumpiausio kelio problema
Trumpiausio kelio problema – grafų teorijos problema, bendru atveju formuluojama kaip radimas tokio kelio tarp dviejų svorinio grafo viršūnių, kad jo briaunų svorių suma būtų mažiausia įmanoma.
Nesvorinis grafas[redaguoti | redaguoti vikitekstą]
Nesvoriniame grafe galima naudoti paiešką į plotį.
Svorinis grafas[redaguoti | redaguoti vikitekstą]
Svarbiausi kelio radimo algoritmai:
- Dijkstros algoritmas naudojamas rasti kelią tarp dviejų viršūnių tokiuose grafuose, kur kiekvienos briaunos svoris ne mažesnis už 0. Algoritmu galima suskaičiuoti ir trumpiausius kelius nuo pradinės viršūnės s iki bet kurios kitos viršūnės.
- Floydo algoritmas (ar Floido-Varšalo algoritmas), randantis trumpiausius kelius tarp kiekvienos viršūnių poros.
- Belmano-Fordo algoritmas, randantis kelius ir tuose grafuose, kur briaunos svoris gali būti neigiamas.
- A* algoritmas – euristinis algoritmas keliui tarp dviejų viršūnių rasti.
Praktikoje naudojamos įvairios jų modifikacijos.