Dijkstrov algoritem

Iz MaFiRaWiki

V podčlanku /METARAM najdete tudi študentski prispevek na to temo,

ki ga želimo združiti s tem člankom.

V podčlanku /NaceMikus najdete tudi študentski prispevek na to temo,

ki ga želimo združiti s tem člankom.

Dijkstrov algoritem (imenovan po E. W. Dijkstra) reši problem iskanja najkrajše poti v usmerjenem grafu G = (V, E), pri čemer je V množica vozlišč, E pa množica povezav. Dolžine vseh povezav so nenegativne.

Dijkstrov algoritem iz podanega grafa in začetnega vozlišča poti vrne najkrajšo pot, ki zajema vsa vozlišča na grafu, ter dolžino te poti. Pravzaprav lahko vrne vse najkrajše poti od izvornega vozlišča do vseh točk v grafu (prirejen algoritem).

Opis algoritma

Za izvedbo algoritma potrebujemo sledeče podatkovne strukture:

  • množico povezanih vozlišč, S
  • seznam najkrajših poti, d
  • drevo prednikov vozlišča, π
  • množico še ne povezanih vozlišč, Q.

Pomembno vlogo ima proces sprosti, ki preverja, če so trenutne razdalje danega vozla sosednjih vozlišč res najkrajše. V primeru, ko bo obstajala krajša razdalja, sprosti osveži obstoječo vrednost.

Algoritem shranjuje za vsako vozlišče v razdaljo d[v], ki je najkrajša razdalja do trenutka, ko pogledamo vanjo. Razdalja d[s] (s je začetno vozlišče) je nič, začetna razdalja vseh ostalih vozlišč pa je nastavljena na neskončno. Slednje temelji na dejstvu, da na začetku ne poznamo nobene poti, ki bi vodila do vseh teh vozlišč. Ob zaključku algoritma je d[v] cena oziroma razdalja najkrajše poti iz s do v, ali pa neskončno, če taka pot ne obstaja.

Dijkstrov algoritem uporablja dve množici vozlišč: S množica vozlišč, čigar najkrajša pot je že določena, ter V - S = Q preostala vozlišča.

Z drugimi besedami - Q je množica nepovezanih, S pa množica povezanih vozlov.

Množica S je na začetku prazna. Ob vsakem koraku se ji dodaja po eno vozlišče, ki se istočasno odstrani iz Q. Ko je vozlišče u dodano v S, algoritem sprosti vse (u, v) povezave, ki peljejo iz ravnokar povezanega vozlišča u.

Psevdokoda

Dijkstra(G, w, s):

  1. inicializiraj (G, s)
  2. S <- 0
  3. Q <- V[G]
  4. while Q != 0 do
  5. u <- izloči minimalni element iz Q
  6. S <- S ∪ {u}
  7. for vsako vozlišče, ki je sosednje u do
  8. sprosti (u, v, w)

Množico Q (nepovezana vozlišča) uredimo v prioritetno vrsto, za katero je znana dolžina vsaj ene poti od začetnega vozlišča.

Na začetku izvedemo inicializacijo - postavimo začetne vrednosti parametrov d (razdalja med vozliščema) na neskončno in π (prednik) na NIL (korak 1). V koraku 2 izpraznimo množico S. V koraku 3 dodamo prioritetni vrsti Q vsa vozlišča V iz grafa G.

Korak 4 opisuje glavno zanko, ki se izvaja, dokler ne dodamo v drevo vseh vozlišč t.j. dokler prioritetna vrsta Q ni prazna. V zanki brišemo vozlišče z najmanjšo prioriteto iz prioritetne vrste Q (korak 5), množici S pa dodamo trenutno vozlišče v grafa G (korak 6). V primeru, da bi iskali le najkrajšo pot od s do t, da torej ne bi bilo zahtevano, da obiščemo vsa vozlišča, bi korak 5 postavili pod pogoj if (u == t)

V prvem izvajanju zanke je u = s (koren). V for zanki (korak 7) vsakemu če obiskanemu vozlišču popravimo razdaljo in prednika (korak 8). V zadnjem koraku - sprostitev - naredimo naslednje: razdalja med vozliščema v in u je w: e d[v] > d[u] + w, potem d[v] = d[u] + w in π[v] = u, sicer se ne zgodi nič.


Sprostitev povezav

Osnovna operacija Dijkstrovega algoritma je sprostitev povezav: če obstaja povezava od u do v, potem je lahko najkrajša znana pot od s do u s tem, da ji na koncu dodamo povezavo (u, v), razširjeno na pot od s do v. Ta pot je dolžine d[u] + w(u, v). Če je dolžin te poti manjša kot d[v], lahko ponastavimo trenutno vrednost d[v] z vrednostjo d[u] + w(u, v).

Sprostitev povezav izvajamo dokler vse vrednosti d[v] ne predstavljajo najkrajšo pot iz s do v. Algoritem deluje tako, da je vsaka povezava (u, v) sproščena le enkrat, to je v trenutku, ko jo dodajamo.

Osebna orodja