Trumpiausio kelio problema

Straipsnis iš Vikipedijos, laisvosios enciklopedijos.
Peršokti į: navigaciją, paiešką

Trumpiausio kelio problemagrafų teorijos problema, bendru atveju formuluojama kaip radimas tokio kelio tarp dviejų svorinio grafo (arba daugiau) viršūnių, kad briaunų svorių suma būtų mažiausia.

Nesvorinis grafas[taisyti | redaguoti kodą]

Nesvoriniame grafe galima naudoti paiešką į gylį (DFS – depth first search) arba paiešką į plotį (BFS – breadth first search).

Svorinis grafas[taisyti | redaguoti kodą]

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 pakankamai efektyviai galima skaič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.