Dijkstra-algoritmus

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.
Kategória	Keresőalgoritmus
Legrosszabb időbonyolultság	$O(|E|+|V|\cdot log|V|)$ $O(|E|+|V|\log |V|)$
Átlagos idő bonyolultság	$O(|E|+|V|\log |V|)$

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).

Az algoritmus menete

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.

Pszeudokód

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.

További információk

• Hajnal Péter: Gráfelmélet, Polygon, Szeged, 1997

Források

• Carla Laffra (Pace University) appletje
• A Boost Graph Library (BGL) implementációja
• A Dijkstra-algoritmus analizálása egy online Javascript IDE-n
• An interactive and visual calculator that lets you define your own nodes
• A Dijkstra-algoritmust pedagógia szempontok figyelembevételével implementáló Java applet
• Animáció a Dijkstra-algoritmusra
• A Dijkstra-algoritmus interaktív implementációja
• A legrövidebb út problémája: Dijkstra-algoritmus
• Dijkstra-algoritmus applet
• Másik applet a Dijkstra-algoritmusra
• Interaktív SVG/ECMAScript példa a Dijkstra-algoritmus demonstrálására
• T-SQL implementáció
• C# Dijkstra-algoritmus implementáció