Dijkstra-algoritmus

A Wikipédiából, a szabad enciklopédiából
A Dijkstra-algoritmus futása egy kis méretű gráfon

A Dijkstra-algoritmus egy mohó algoritmus, amivel irányított vagy irányitá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 p csúcspontja a G gráfnak. A p pont az út kiindulási pontja. Jelöljük V-vel a G gráf csúcspontjainak a halmazát, és legyen (u,v) a G gráf u-t v-vel összekötő éle, ahol u, v a gráf pontjai. 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 pontból a v pontba való eljutás költsége. Az élekhez rendelt költségeket tekinthetjük a két pont közötti távolság általánosításának. Két pont közötti út költsége az úton lévő élek költségének az összege. Adott s és t V-beli pontpárra 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.

Tartalomjegyzék

Az algoritmus menete [szerkesztés]

Az algoritmus a futása során a G gráf minden egyes v csúcspontjá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 pontjá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 ponthalmazokkal dolgozik. Az S halmaz tartalmazza G gráfnak azokat a pontjait, 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úcspontját. Az S halmaz kezdetben az üres halmaz, és az algoritmus minden egyes iterációja során egy csúcspont átkerül a Q halmazból az S halmazba. Ezt a csúcspontot úgy választjuk, hogy ennek legyen a legalacsonyabb a d[u] értéke. Amikor az u csúcspont á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 [szerkesztés]

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, source):
 2     for each vertex v in Graph:           // Initializations
 3         dist[v] := infinity               // Unknown distance function from s to v
 4         previous[v] := undefined
 5     dist[source] := 0                     // Distance from s to s
 6     Q := copy(Graph)                      // Set of all unvisited vertices
 7     while Q is not empty:                 // The main loop
 8         u := extract_min(Q)               // Remove best vertex from priority queue; returns source on first iteration
 9         for each neighbor v of u:
10             alt = dist[u] + length(u, v)
11             if alt < dist[v]              // Relax (u,v)
12                 dist[v] := alt
13                 previous[v] := u

Ha csak a source kezdőpont és a target végpont közötti legrövidebb út érdekel minket, akkor befejezhetjük a keresést a 9-es sorban, ha u = target teljesül. Ekkor a source-ból a target-be vezető legrövidebb utat a következő iterációval olvashatjuk ki:

1 S := empty sequence
2 u := target
3 while defined previous[u]
4     insert u at the beginning of S
5     u := previous[u]

Ekkor az S sorozat a source-ból a target-be vezető legrövidebb utak egyikének csúcspontjait tartalmazó lista, vagy pedig üres sorozat, ha nem létezik ilyen út.

Általánosabb problémát kapunk, ha a source és target 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.

Hivatkozások [szerkesztés]

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

Források [szerkesztés]

A lap eredeti címe: „http://hu.wikipedia.org/w/index.php?title=Dijkstra-algoritmus&oldid=13181941”