útvonalkeresés

Az útvonalkeresés egy gráfelméleti feladat, amelyben két csúcs között keresünk útvonalat egy költségfüggvény alapján. Gyakori cél a legrövidebb út megtalálása, de előfordulhat több kritérium vagy korlátozás is (idő, energia, útvonalak hossza). A gráf lehet irányított vagy irányítatlan; élek súlya pozitív vagy szükség szerint negatív is lehet.

Formálisan G=(V,E) gráf és súlyfüggvény w:E→R. Egy út költsége a felépítő élek súlyainak összege. A feladatok közé tartozik a single-source shortest path (egy forrásból minden másig), az all-pairs shortest path (minden pár közötti legrövidebb út), vagy a k-shortest útvonalak keresése.

Főbb algoritmusok közé tartozik a Dijkstra, amely pozitív súlyú élek esetén adja a legrövidebb utakat egy forrásból; az A* keresés heurisztikával irányítja a találgatást, és adott heurisztikával optimális marad; a Bellman-Ford negatív súlyú élekre is működik, de nincs negatív ciklus; a Floyd-Warshall minden-pár legrövidebb utat számol O(n^3) időben; BFS egyszerűbb megoldás súly nélküli vagy egységsúlyú gráfokra. K-útvonalak esetén ismertek kifejezetten kiterjesztések, például Yen- vagy Eppstein-algoritmusok.

Adatszerkezetek és komplexitás: általában adjacency lista vagy mátrix; prioritási sor (min-heap) segíti a Dijkstra/A* futását. Alkalmazások között szerepel a navigáció, robotika, hálózati útvonal-irányítás, logisztika és számítógépes játékok. Történeti mérföldkövek közé tartozik Dijkstra 1959-es, Bellman-Ford 1958–59-es és Floyd-Warshall 1962-es hozzájárulások, valamint az A* algoritmus 1968-as megjelenése.