PgRouting

Algoritmusok

Dijkstra algoritmus

A Dijkstra algoritmus egy súlyozott élű, irányított $G=(V,E)$ gráf adott csúcsából egy másik adott csúcsába vezető legrövidebb út megtalálására szolgáló módszer. Az algoritmus csak nem negatív élsúlyok esetén működik. Jelölje a súlyfüggvényt $w$. Az algoritmus mohó módszert használ. Legyen a kiindulási pont $s$, a célállomás pedig $t$. Az algoritmus egy $H$ halmazban tárolja azon csúcsokat, amelyeknek már ismerjük az $s$-ből hozzájuk vezető legrövidebb út hosszát. Ezen kívül minden $u$ csúcsról nyilvántartunk az algoritmus futása során egy $D[u]$ értéket, ami az $s$-ből $u$-ba vezető addig megismert legrövidebb út hossza.

Kezdetben $H$ üres, $D[s]=0$ és minden más $v$ csúcsra $D[v]=\mathrm{\infty }$. Ezután minden iterációban kiválasztunk a $V\setminus H$ halmazból egy olyan $x$ csúcsot, amelyre $D[x]$ minimális, áttesszük $x$-et $H$-ba, majd $x$ minden olyan $v$ szomszédjára, amely nincs $H$-ban frissítjük a $D[v]$ értéket: $D[v]=\min \{D[v],D[x]+w(x,v)\}$. Az algoritmus véget ér, amikor $t$ átkerül $H$-ba, ekkor $D[t]$ egy legrövidebb $s$-ből $t$-be vezető út hossza. Az algoritmus kis módosítással egy legrövidebb utat is megad $s$-ből $t$-be.

Az algoritmus költsége szomszédsági mátrixos gráfábrázolás esetén $O(|V{|}^2)$, szomszédsági listás gráfábrázolás esetén Fibonacci kupacot használva $O(|E|+|V|\log |V|)$.

Kétirányú Dijkstra algoritmus

A kétirányú Dijkstra algoritmus szintén egy súlyozott élű, irányított $G=(V,E)$ gráf adott csúcsából egy másik adott csúcsába vezető legrövidebb út megtalálására szolgáló módszer. Az algoritmus csak nem negatív élsúlyok esetén működik. Legyen a kiindulási pont $s$, a célállomást pedig $t$. A Dijkstra algoritmust futtatjuk a kiindulási pontból az eredeti gráfon, és párhuzamosan a célállomásból a transzponált gráfon (amelyet úgy kapunk az eredeti gráfból, hogy az élek irányítását megfordítjuk). Akkor állunk meg, ha egy $v$ csúcs mindkét irányból bekerül a Dijkstra algoritmusnál definiált $H$ halmazba (pontosabban a $H_s$ és a $H_t$ halmazba is). Egy alternatív lehetőség, hogy a $H_s$ és a $H_t$ halmazok közül minden egyes iterációban csak azt bővítjük, amelyiknél $D[x]$ kisebb. Az algoritmus kis módosítással egy legrövidebb utat is megad $s$-ből $t$-be.

k-Dijkstra algoritmus

A $k$-Dijkstra algoritmus egy súlyozott élű, irányított $G=(V,E)$ gráf adott csúcsából több adott csúcsába vezető legrövidebb út megtalálására szolgáló módszer. Valójában a Dijkstra algoritmus a gráf egy adott csúcsából az összes többi csúcsba vezető legrövidebb utat megtalálja, így akárhány célállomást megadhatunk. Az algoritmus akkor fejeződik be, amikor minden egyes célállomás bekerült a Dijkstra algoritmusnál definiált $H$ halmazba. Az algoritmus kis módosítással magukat a legrövidebb utakat is megadja.

Az algoritmus költsége szomszédsági mátrixos gráfábrázolás esetén $O(|V{|}^2)$, szomszédsági listás gráfábrázolás esetén Fibonacci kupacot használva $O(|E|+|V|\log |V|)$.

A* algoritmus

Az $A^{\ast }$ algoritmus egy súlyozott élű, irányított $G=(V,E)$ gráf adott csúcsából egy másik adott csúcsába vezető legrövidebb út megtalálására szolgáló módszer. Az $A^{\ast }$ algoritmus a Dijkstra algoritmus általánosítása, és szintén csak nem negatív élsúlyok esetén működik. Jelölje a súlyfüggvényt $w$. Az algoritmus mohó módszert használ. Legyen a kiindulási pont $s$, a célállomás pedig $t$. Az algoritmus egy $H$ halmazban tárolja azon csúcsokat, amelyeknek már ismerjük az $s$-ből hozzávezető legrövidebb út hosszát, egy $M$ halmazban pedig azokat, amelyeket már elértünk $s$-ből, de az $s$-ből hozzájuk vezető legrövidebb út hosszát még nem ismerjük. Minden $u$ csúcsról nyilvántartunk az algoritmus futása során három értéket: $D[u]$ az $s$-ből $u$-ba vezető addig megismert legrövidebb út hossza, $C[u]$ egy nem negatív heurisztikus alsó becslés az $u$-ból $t$-be vezető legrövidebb út hosszára, amelyre az is teljesül, hogy az $u$-ból bármely $v$ csúcsba vezető legrövidebb út hosszára $C[u]-C[v]$ alsó korlát (például egy térkép esetén $u$ és $t$ légvonalban mért távolsága), végül $B[u]=D[u]+C[u]$.

Kezdetben $H$ üres, $M$-ben csak az $s$ csúcs van, és $B[s]=0$. Ezután minden iterációban kiválasztunk az $M$ halmazból egy olyan $x$ csúcsot, amelyre $B[x]$ minimális, áttesszük $x$-et $H$-ba, majd $x$ minden olyan $v$ szomszédjára, amely nincs $H$-ban frissítjük először a $D[v]$ értéket: $D[v]=\min \{D[v],D[x]+w(x,v)\}$, majd a $B[v]$ értéket: $B[v]=\min \{B[v],D[v]+C[v]\}$, végül áttesszük $v$-t $M$-be. Az algoritmus véget ér, amikor $t$ átkerül $M$-ből $H$-ba, ekkor $B[t]$ egy legrövidebb $s$-ből $t$-be vezető út hossza. Az algoritmus kis módosítással egy legrövidebb utat is megad $s$-ből $t$-be.

A tapasztalat azt mutatja, hogy az $A^{\ast }$ algoritmus számos esetben hatékonyabb, mint a Dijkstra algoritmust.

Kétirányú $A^{\ast }$ algoritmus

A kétirányú $A^{\ast }$ algoritmus egy súlyozott élű, irányított $G=(V,E)$ gráf adott csúcsából egy másik adott csúcsába vezető legrövidebb út megtalálására szolgáló módszer. Az algoritmus csak nem negatív élsúlyok esetén működik. Legyen a kiindulási pont $s$, a célállomást pedig $t$. Az $A^{\ast }$ algoritmust futtatjuk a kiindulási pontból az eredeti gráfon, és párhuzamosan a célállomásból a transzponált gráfon (amelyet úgy kapunk az eredeti gráfból, hogy az élek irányítását megfordítjuk). Akkor állunk meg, ha egy $v$ csúcs mindkét irányból bekerül az $A^{\ast }$ algoritmusnál definiált $H$ halmazba (pontosabban a $H_s$ és a $H_t$ halmazba is). Az algoritmus kis módosítással egy legrövidebb utat is megad s-ből t-be.

Yen algoritmus

A Yen algoritmus egy súlyozott élű, irányított $G=(V,E)$ gráf egy adott csúcsából egy adott másik csúcsába vezető legrövidebb út mellett megtalálja a második, harmadik, …, $k$-adik legrövidebb (egyszerű) utat is. Az algoritmus csak nem negatív élsúlyok esetén működik.

Az algoritmus költsége $O(k|V|(|E|+|V|\log |V|))$.

Floyd-Warshall algoritmus

A Floyd-Warshall algoritmus egy súlyozott élű, irányított $G=(V,E)$ gráf bármely két csúcsa közötti legrövidebb út megtalálására szolgáló módszer. Az algoritmus negatív élsúlyok esetén is működik, ha a gráf nem tartalmaz negatív összhosszúságú irányított kört. Jelölje a súlyfüggvényt $w$. Az algoritmus dinamikus programozást használ. Legyen a gráf csúcshalmaza $\{v_1,v_2,\dots ,v_n\}$. Az algoritmus minden $0⩽k⩽n$ esetén meghatározza a $v_i$-ből $v_j$-be menő legrövidebb olyan (egyszerű) út $T_k[v_i,v_j]$ hosszát, amelyen a közbülső csúcsok a $\{v_1,v_2,\dots ,v_k\}$ halmazból kerülnek ki: $T_0[v_i,v_j]=w(v_i,v_j)$, és $T_k[v_i,v_j]=\min \{T_{k-1}[v_i,v_j],T_{k-1}[v_i,v_k]+T_{k-1}[v_k,v_j]\}$ ha $k>0$. Az algoritmus kis módosítással magukat a legrövidebb utakat is megadja.

Az algoritmus költsége $O(|V{|}^3)$.

Johnson algoritmus

A Johnson algoritmus egy súlyozott élű, irányított $G=(V,E)$ gráf bármely két csúcsa közötti legrövidebb út megtalálására szolgáló módszer. Az algoritmus negatív élsúlyok esetén is működik, ha a gráf nem tartalmaz negatív összhosszúságú irányított kört. Jelölje a súlyfüggvényt $w$. Az algoritmus ritka gráfokon teljesít igazán jól.

Vegyünk fel egy új $s$ csúcsot, és vezessünk $s$-ből nulla súlyú éleket $G$ csúcsaiba. Jelölje az így kapott gráfot $G^{\prime }$. Futtassuk le $G^{\prime }$-re a Bellman-Ford algoritmust az $s$ kezdőcsúccsal. Az algoritmus által szolgáltatott távolságérték a gráf egy $v$ csúcsára legyen $D[v]$. Átsúlyozzuk a $G$ gráf éleit: legyen $w^{\prime }(u,v)=w(u,v)+D[u]-D[v]$ minden $(u,v)$ élre. Most $w^{\prime }$ egy nem negatív súlyfüggvény $G$-n. Futtassuk ezzel a súlyfüggvénnyel a Dijkstra algoritmust a $G$ gráf minden csúcsából. Egy legrövidebb $u$-ból $v$-be vezető út hossza ezután a kapott érték mínusz $D[u]-D[v]$. Az algoritmus kis módosítással magukat a legrövidebb utakat is megadja.

Az algoritmus költsége szomszédsági listás gráfábrázolás esetén Fibonacci kupacot használva $O(|V|(|E|+|V|\log |V|))$.

Utazó ügynök probléma

Az utazó ügynök probléma a következő. Adott városoknak egy listája, és adott bármely két város között a távolság. Határozzunk meg egy olyan körutat, amely minden városon pontosan egyszer halad át, és a hossza minimális. A problémára nem ismert polinomiális költségű algoritmus. A program ún. simulated annealing technikán alapuló algoritmust használ egy jó közelítő megoldás meghatározására.

Legrövidebb utak kanyarodási korlátokkal

Az algoritmus egy súlyozott élű, irányított $G=(V,E)$ gráf adott csúcsából egy másik adott csúcsába vezető legrövidebb út meghatározásakor képes figyelembe venni, hogy két csatlakozó él egymás utáni bejárása extra költséggel bírhat. Ezeket a megszorításokat egy külön táblában adhatjuk meg. Tapasztalat szerint az algoritmus közel olyan gyors, mint az $A^{\ast }$ algoritmus.

Vezetési távolság

Egy súlyozott élű, irányított $G=(V,E)$ gráfban a Dijkstra algoritmus felhasználásával megadja azon csúcsokat, melyekbe egy vagy több adott csúcsból egy adott értéknél rövidebb úton el lehet jutni.