Trumpiausio kelio problema

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.

Užduotis apskaičiuoti trumpiausią tam tikro grafo kelią yra optimizavimo problema ir dažnai literatūroje vadinama kaip trumpiausio kelio problema.[1]

Nesvorinis grafas redaguoti

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

Svorinis grafas redaguoti

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.

Šaltiniai redaguoti

  1. Korte, Bernhard; Vygen, Jens (2007-11-04). Combinatorial Optimization. Berlin Heidelberg: Springer Science & Business Media. ISBN 978-3-540-71844-4.