V teoriji grafov je problem najkrajših poti problem iskanja poti med dvema točkama v grafu, tako da je vsota uteži povezav, ki sestavljajo to pot, čim manjša.
Problem iskanja najkrajše poti med dvema križiščema na cestnem zemljevidu lahko modeliramo kot poseben primer problema najkrajše poti v grafih, kjer točke ustrezajo križiščem, povezave pa odsekom ceste, pri čemer je vsak odsek utežen z dolžino ali razdaljo.
Definicija Problem najkrajše poti lahko definiramo za grafe, ne glede na to, ali so neusmerjeni, usmerjeni ali mešani. Definicija neusmerjenih grafov pravi, da je mogoče vsako povezavo prečkati v katero koli smer. Usmerjeni grafi zahtevajo, da so zaporedne točke na poti povezane z ustrezno usmerjeno povezavo.
Dve točki sta sosednji, če sta obe incidenčni na skupno povezavo. Pot v neusmerjenem grafu je zaporedje točk , tako da je soseda točke za vse . Takšna pot se imenuje pot dolžine od do . ( so spremenljivke; njihovo oštevilčenje se nanaša na njihov položaj v zaporedju in ni nujno povezano s kanoničnim označevanjem.)
Naj bo , kjer je povezava, ki je incidenčna tako na kot na . Za dano utežno funkcijo in neusmerjen (preprost) graf je najkrajša pot od do tista pot (kjer je in ), ki po vseh možnih poteh od do minimizira vsoto Če ima vsaka povezava v grafu težo 1 oz. , je to enakovredno iskanju poti z najmanjšim številom povezav.
Problem se včasih imenuje tudi problem najkrajše poti za en par točk, da se loči od naslednjih različic: Problem najkrajše poti z enim izvorom, pri katerem moramo najti najkrajše poti od izvornega točke v do vseh drugih točk v grafu. Problem najkrajše poti z enim ciljem, pri katerem moramo najti najkrajše poti od vseh točk v usmerjenem grafu do ene same ciljne točke v. To je mogoče prevesti na problem najkrajše poti z enim izvorom z obrnitvijo povezav v usmerjenem grafu. Problem najkrajše poti med vsemi pari točk, pri katerem moramo najti najkrajše poti med vsakim parom točk v, v' v grafu.
Te posplošitve imajo bistveno učinkovitejše algoritme kot poenostavljen pristop izvajanja algoritma najkrajše poti z enim parom na vseh ustreznih parih vozlišč.
Sklici
Viri Načrtovanje podatkovnih struktur in algoritmov, Igor Kononeko, UL-FRI 1996, ISBN 961-6209-02-7
Kategorija:Algoritmi