== Algoritmusok ==

=== Dijkstra algoritmus ===
A Dijkstra algoritmus egy súlyozott élű, irányított <math>G=(V,E)</math> 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 <math>w</math>. Az algoritmus mohó módszert használ. Legyen a kiindulási pont <math>s</math>, a célállomás pedig <math>t</math>. Az algoritmus egy <math>H</math> halmazban tárolja azon csúcsokat, amelyeknek már ismerjük az <math>s</math>-ből hozzájuk vezető legrövidebb út hosszát. Ezen kívül minden <math>u</math> csúcsról nyilvántartunk az algoritmus futása során egy <math>D[u]</math> értéket, ami az <math>s</math>-ből <math>u</math>-ba vezető addig megismert legrövidebb út hossza.

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

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

=== Kétirányú Dijkstra algoritmus ===
A kétirányú Dijkstra algoritmus szintén egy súlyozott élű, irányított <math>G=(V,E)</math> 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 <math>s</math>, a célállomást pedig <math>t</math>. 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 <math>v</math> csúcs mindkét irányból bekerül a Dijkstra algoritmusnál definiált <math>H</math> halmazba (pontosabban a <math>H_s</math> és a <math>H_t</math> halmazba is). Egy alternatív lehetőség, hogy a <math>H_s</math> és a <math>H_t</math> halmazok közül minden egyes iterációban csak azt bővítjük, amelyiknél <math>D[x]</math> kisebb. Az algoritmus kis módosítással egy legrövidebb utat is megad <math>s</math>-ből <math>t</math>-be.

=== k-Dijkstra algoritmus ===
A <math>k</math>-Dijkstra algoritmus egy súlyozott élű, irányított <math>G=(V,E)</math> 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 <math>H</math> 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 <math>O(|V|^2)</math>, szomszédsági listás gráfábrázolás esetén Fibonacci kupacot használva
<math>O(|E|+|V|\log |V|)</math>.

=== A* algoritmus ===
Az <math>A^\ast</math> algoritmus egy súlyozott élű, irányított <math>G=(V,E)</math> 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 <math>A^\ast</math> 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 <math>w</math>. Az algoritmus mohó módszert használ. Legyen a kiindulási pont <math>s</math>, a célállomás pedig <math>t</math>. Az algoritmus egy <math>H</math> halmazban tárolja azon csúcsokat, amelyeknek már ismerjük az <math>s</math>-ből hozzávezető legrövidebb út hosszát, egy <math>M</math> halmazban pedig azokat, amelyeket már elértünk <math>s</math>-ből, de az <math>s</math>-ből hozzájuk vezető legrövidebb út hosszát még nem ismerjük. Minden <math>u</math> csúcsról nyilvántartunk az algoritmus futása során három értéket: <math>D[u]</math> az <math>s</math>-ből <math>u</math>-ba vezető addig megismert legrövidebb út hossza, <math>C[u]</math> egy nem negatív heurisztikus alsó becslés az <math>u</math>-ból <math>t</math>-be vezető legrövidebb út hosszára, amelyre az is teljesül, hogy az <math>u</math>-ból bármely <math>v</math> csúcsba vezető legrövidebb út hosszára
<math>C[u]-C[v]</math> alsó korlát (például egy térkép esetén <math>u</math> és <math>t</math> légvonalban mért távolsága), végül <math>B[u]=D[u]+C[u]</math>.

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

A tapasztalat azt mutatja, hogy az <math>A^\ast</math> algoritmus számos esetben hatékonyabb, mint a Dijkstra algoritmust.

=== Kétirányú <math>A^\ast</math> algoritmus ===
A kétirányú <math>A^\ast</math> algoritmus egy súlyozott élű, irányított <math>G=(V,E)</math> 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 <math>s</math>, a célállomást pedig <math>t</math>. Az <math>A^\ast</math> 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 <math>v</math> csúcs mindkét irányból bekerül az <math>A^\ast</math> algoritmusnál definiált <math>H</math> halmazba (pontosabban a <math>H_s</math> és a <math>H_t</math> 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 <math>G=(V,E)</math> 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, …, <math>k</math>-adik legrövidebb (egyszerű) utat is. Az algoritmus csak nem negatív élsúlyok esetén működik.

Az algoritmus költsége
<math>O(k|V|(|E|+|V|\log |V|))</math>.

=== Floyd-Warshall algoritmus ===
A Floyd-Warshall algoritmus egy súlyozott élű, irányított <math>G=(V,E)</math> 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 <math>w</math>. Az algoritmus dinamikus programozást használ. Legyen a gráf csúcshalmaza <math>\{v_1,v_2,\ldots,v_n\}</math>. Az algoritmus minden <math>0\leqslant k\leqslant n</math> esetén meghatározza a <math>v_i</math>-ből
<math>v_j</math>-be menő legrövidebb olyan (egyszerű) út <math>T_k[v_i,v_j]</math> hosszát, amelyen a közbülső csúcsok a <math>\{v_1,v_2,\ldots,v_k\}</math> halmazból kerülnek ki:
<math>T_0[v_i,v_j]=w(v_i,v_j)</math>, és <math>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]\}</math> ha <math>k>0</math>. Az algoritmus kis módosítással magukat a legrövidebb utakat is megadja.

Az algoritmus költsége <math>O(|V|^3)</math>.

=== Johnson algoritmus ===
A Johnson algoritmus egy súlyozott élű, irányított <math>G=(V,E)</math> 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 <math>w</math>. Az algoritmus ritka gráfokon teljesít igazán jól.

Vegyünk fel egy új <math>s</math> csúcsot, és vezessünk <math>s</math>-ből nulla súlyú éleket <math>G</math> csúcsaiba. Jelölje az így kapott gráfot <math>G'</math>. Futtassuk le <math>G'</math>-re a Bellman-Ford algoritmust az <math>s</math> kezdőcsúccsal. Az algoritmus által szolgáltatott távolságérték a gráf egy <math>v</math> csúcsára legyen
<math>D[v]</math>. Átsúlyozzuk a <math>G</math> gráf éleit: legyen <math>w'(u,v)=w(u,v)+D[u]-D[v]</math> minden <math>(u,v)</math> élre. Most <math>w'</math> egy nem negatív súlyfüggvény <math>G</math>-n. Futtassuk ezzel a súlyfüggvénnyel a Dijkstra algoritmust a <math>G</math> gráf minden csúcsából. Egy legrövidebb <math>u</math>-ból <math>v</math>-be vezető út hossza ezután a kapott érték mínusz <math>D[u]-D[v]</math>. 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
<math>O(|V|(|E|+|V|\log |V|))</math>.

=== 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 <math>G=(V,E)</math> 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 <math>A^\ast</math> algoritmus.

=== Vezetési távolság ===
Egy súlyozott élű, irányított <math>G=(V,E)</math> 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.

PgRouting

2016-04-10T09:51:45Z

Benek: Új oldal, tartalma: „== Algoritmusok == '''Dijkstra algoritmus''' (Shortest Path Dijkstra) A Dijkstra algoritmus egy súlyozott élű, irányított <math>G=(V,E)</math> gráf adott csúc…”

== Algoritmusok ==

'''Dijkstra algoritmus'''
(Shortest Path Dijkstra)

A Dijkstra algoritmus egy súlyozott élű, irányított <math>G=(V,E)</math> 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 <math>w</math>. Az algoritmus mohó módszert használ. Legyen a kiindulási pont <math>s</math>, a célállomás pedig <math>t</math>. Az algoritmus egy <math>H</math> halmazban tárolja azon csúcsokat, amelyeknek már ismerjük az <math>s</math>-ből hozzájuk vezető legrövidebb út hosszát. Ezen kívül minden <math>u</math> csúcsról nyilvántartunk az algoritmus futása során egy <math>D[u]</math> értéket, ami az <math>s</math>-ből <math>u</math>-ba vezető addig megismert legrövidebb út hossza.

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

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

'''Kétirányú Dijkstra algoritmus'''
(Bi-directional Dijkstra Shortest Path)

A kétirányú Dijkstra algoritmus szintén egy súlyozott élű, irányított <math>G=(V,E)</math> 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 <math>s</math>, a célállomást pedig <math>t</math>. 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 <math>v</math> csúcs mindkét irányból bekerül a Dijkstra algoritmusnál definiált <math>H</math> halmazba (pontosabban a <math>H_s</math> és a <math>H_t</math> halmazba is). Egy alternatív lehetőség, hogy a <math>H_s</math> és a <math>H_t</math> halmazok közül minden egyes iterációban csak azt bővítjük, amelyiknél <math>D[x]</math> kisebb. Az algoritmus kis módosítással egy legrövidebb utat is megad <math>s</math>-ből <math>t</math>-be.

'''<math>k</math>-Dijkstra algoritmus'''
(<math>k</math>-Dijkstra, One to Many Shortest Path)

A <math>k</math>-Dijkstra algoritmus egy súlyozott élű, irányított <math>G=(V,E)</math> 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 <math>H</math> 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 <math>O(|V|^2)</math>, szomszédsági listás gráfábrázolás esetén Fibonacci kupacot használva
<math>O(|E|+|V|\log |V|)</math>.

'''<math>A^\ast</math> algoritmus'''
(Shortest Path <math>A^\ast</math>)

Az <math>A^\ast</math> algoritmus egy súlyozott élű, irányított <math>G=(V,E)</math> 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 <math>A^\ast</math> 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 <math>w</math>. Az algoritmus mohó módszert használ. Legyen a kiindulási pont <math>s</math>, a célállomás pedig <math>t</math>. Az algoritmus egy <math>H</math> halmazban tárolja azon csúcsokat, amelyeknek már ismerjük az <math>s</math>-ből hozzávezető legrövidebb út hosszát, egy <math>M</math> halmazban pedig azokat, amelyeket már elértünk <math>s</math>-ből, de az <math>s</math>-ből hozzájuk vezető legrövidebb út hosszát még nem ismerjük. Minden <math>u</math> csúcsról nyilvántartunk az algoritmus futása során három értéket: <math>D[u]</math> az <math>s</math>-ből <math>u</math>-ba vezető addig megismert legrövidebb út hossza, <math>C[u]</math> egy nem negatív heurisztikus alsó becslés az <math>u</math>-ból <math>t</math>-be vezető legrövidebb út hosszára, amelyre az is teljesül, hogy az <math>u</math>-ból bármely <math>v</math> csúcsba vezető legrövidebb út hosszára
<math>C[u]-C[v]</math> alsó korlát (például egy térkép esetén <math>u</math> és <math>t</math> légvonalban mért távolsága), végül <math>B[u]=D[u]+C[u]</math>.

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

A tapasztalat azt mutatja, hogy az <math>A^\ast</math> algoritmus számos esetben hatékonyabb, mint a Dijkstra algoritmust.

'''Kétirányú <math>A^\ast</math> algoritmus'''
(Bi-directional <math>A^\ast</math> Shortest Path)

A kétirányú <math>A^\ast</math> algoritmus egy súlyozott élű, irányított <math>G=(V,E)</math> 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 <math>s</math>, a célállomást pedig <math>t</math>. Az <math>A^\ast</math> 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 <math>v</math> csúcs mindkét irányból bekerül az <math>A^\ast</math> algoritmusnál definiált <math>H</math> halmazba (pontosabban a <math>H_s</math> és a <math>H_t</math> halmazba is). Az algoritmus kis módosítással egy legrövidebb utat is megad s-ből t-be.

'''Yen algoritmus'''
(<math>k</math>-Shortest Path, Multiple Alternative Paths)

A Yen algoritmus egy súlyozott élű, irányított <math>G=(V,E)</math> 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, …, <math>k</math>-adik legrövidebb (egyszerű) utat is. Az algoritmus csak nem negatív élsúlyok esetén működik.

Az algoritmus költsége
<math>O(k|V|(|E|+|V|\log |V|))</math>.

'''Floyd-Warshall algoritmus'''
(Floyd-Warshall Algorithm, All Pairs Shortest Path)

A Floyd-Warshall algoritmus egy súlyozott élű, irányított <math>G=(V,E)</math> 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 <math>w</math>. Az algoritmus dinamikus programozást használ. Legyen a gráf csúcshalmaza <math>\{v_1,v_2,\ldots,v_n\}</math>. Az algoritmus minden <math>0\leqslant k\leqslant n</math> esetén meghatározza a <math>v_i</math>-ből
<math>v_j</math>-be menő legrövidebb olyan (egyszerű) út <math>T_k[v_i,v_j]</math> hosszát, amelyen a közbülső csúcsok a <math>\{v_1,v_2,\ldots,v_k\}</math> halmazból kerülnek ki:
<math>T_0[v_i,v_j]=w(v_i,v_j)</math>, és <math>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]\}</math> ha <math>k>0</math>. Az algoritmus kis módosítással magukat a legrövidebb utakat is megadja.

Az algoritmus költsége <math>O(|V|^3)</math>.

'''Johnson algoritmus'''
(Johnson’s Algorithm, All Pairs Shortest Path)

A Johnson algoritmus egy súlyozott élű, irányított <math>G=(V,E)</math> 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 <math>w</math>. Az algoritmus ritka gráfokon teljesít igazán jól.

Vegyünk fel egy új <math>s</math> csúcsot, és vezessünk <math>s</math>-ből nulla súlyú éleket <math>G</math> csúcsaiba. Jelölje az így kapott gráfot <math>G'</math>. Futtassuk le <math>G'</math>-re a Bellman-Ford algoritmust az <math>s</math> kezdőcsúccsal. Az algoritmus által szolgáltatott távolságérték a gráf egy <math>v</math> csúcsára legyen
<math>D[v]</math>. Átsúlyozzuk a <math>G</math> gráf éleit: legyen <math>w'(u,v)=w(u,v)+D[u]-D[v]</math> minden <math>(u,v)</math> élre. Most <math>w'</math> egy nem negatív súlyfüggvény <math>G</math>-n. Futtassuk ezzel a súlyfüggvénnyel a Dijkstra algoritmust a <math>G</math> gráf minden csúcsából. Egy legrövidebb <math>u</math>-ból <math>v</math>-be vezető út hossza ezután a kapott érték mínusz <math>D[u]-D[v]</math>. 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
<math>O(|V|(|E|+|V|\log |V|))</math>.

'''Utazó ügynök probléma'''
(Traveling Sales Person)

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'''
(Turn Restriction Shortest Path (TRSP))

Az algoritmus egy súlyozott élű, irányított <math>G=(V,E)</math> 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 <math>A^\ast</math> algoritmus.

'''Vezetési távolság'''
(Driving Distance)

Egy súlyozott élű, irányított <math>G=(V,E)</math> 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.