Trumpiausio kelio problema

Straipsnis iš Vikipedijos, laisvosios enciklopedijos.
Jump to navigation Jump to search

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[redaguoti | redaguoti vikitekstą]

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

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 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.