Najkratšia cesta
V teórii grafov je problém najkratšej cesty hľadanie takej cesty medzi dvoma vrcholmi, že súčet ohodnotení hrán na tejto ceste je najmenší zo všetkých možných ciest medzi týmito vrcholmi. Je to štandardný problém napríklad pri hľadaní čo najkratšej cesty medzi dvoma mestami na mape.
^ TOPTypy
Problém najkratšej cesty má dve zovšeobecnenia.
- Single-source shortest path problem
- Toto zovšobecnenie hľadá všetky najkratšie cesty z jedného daného vrcholu do všetkých ostatných vrcholov v grafe. Príkladom takého algoritmu je Dijkstrov algoritmus.
- All-pairs shortest path problem
- V tomto zovšeobecnení hľadáme najkratšie cesty medzi všetkými dvojicami vrcholov v grafe. Algoritmus Floyd-Warshall je známym príkladom ako riešiť tento problém.
Použitie
Ak by sme reprezentovali nedeterministický abstraktný stroj ako graf, kde vrcholy popisujú stavy a hrany popisujú možné prechody medzi nimi, môžeme použiť algoritmus hľadania najkratšej cesty na nájdenie optimálnej postupnosti prechodov na dosiahnutie daného cieľa. Napríklad by vrcholy predstavovali všetky možné stavy Rubikovej kocky a každá orientovaná hrana by zodpovedala jednému pohybu na kocke. Potom nájdenie najkratšej cesty by znamenalo nájsť riešenie, ktoré používa najmenší možný počet pohybov na kocke.
^ TOP