Johnsonov algoritem

Iz MaFiRaWiki

Ta članek ali del članka je v delu. Veseli bomo, če ga boste dopolnili in popravili.

Kaj pomeni to opozorilo?

Johnsonov algoritem reši problem iskanja najkrajših poti med vsemi pari vozlišč v redkem, uteženem in usmerjenem grafu. Uteži so poljubna realna števila.

Vsebina

Ideja algoritma

Imamo usmerjen in utežen graf. Uteži so poljubna realna števila w.

Določimo nove uteži w' tako, da bo veljalo:

  • najkrajša pot v grafu z utežmi w je pravtako najkrajša pot v grafu z utežmi w'
  • nove uteži so nenegativne

Nato |V|-krat izvedemo Dijkstrov algoritem, kjer je vsako vozlišče enkrat izhodiščno vozlišče, za izračun najkrajših poti med vsemi pari vozlišč. Dobimo pravo pot, le teže najkrajših poti popravimo za razliko ww'.

Potek algoritma

Imamo usmerjen in utežen graf G = (V,E). Uteži so poljubna realna števila w.

Algoritem vrne matriko najkrajših poti za vse pare vozlišč ali sporoči, da vhodni graf vsebuje negativen cikel.

Z Bellman-Fordovim algoritmom preveri, če graf vsebuje negativen cikel. Če graf ne vsebuje negativnega cikla, izračuna nove nenegativne uteži w' z metodo reweigthing. Nato |V|-krat izvede Dijkstrov algoritem, kjer je vsako vozlišče enkrat izhodiščno vozlišče, za izračun najkrajših poti med vsemi pari vozlišč. Na koncu popravi dobljene teže najkrajših poti za razliko ww'.

Reweighting

Imamo usmerjen, utežen garaf G = (V,E). Uteži so poljubna realna števila w. Radi bi, da so vse uteži na povezavah nenegativne. Naredimo novi graf G' = (V',E'), kjer je V' = V + s za neko novo vozlišče s, ki ni iz V in E' = E + (s,v):v iz V ter w(s,v) = 0 za vse v iz V. Ker novo vozlišče s nima vhodnih povezav, obstajajo le tiste najkrajše poti z izhodiščnim vozliščem s. Definiramo h(v) = d(s,v) je najkrajša pot od vozlišča s do vozlišča v za vse v iz V.
Velja h(v) < = h(u) + w(u,v) za vse povezave (u,v) iz E'. Nove uteži w' izračunamo s formulo w'(u,v) = w(u,v) + h(u) − h(v).

Shema algoritma

JOHNSON(G)
pridela G', kjer V(G') = V(G) + {s},
  E'(G) = E(G) + {(s,v): v iz V(G)} in
  w(s,v) = 0 za vse v iz V(G)
if BELLMAN-FORD(G',w,s) = FALSE
  then print "Vhodni graf vsebuje negativen cikel."
else for vsak v iz V(G') do
  h(v) = d(s,v) %izračunane z Bellman-Fordovim algoritmom
end for
for vsak (u,v) iz E(G') do
  w'(u,v) = w(u,v) + h(u) - h(v)
end for
for vsak u iz V(G) do
  DIJKSTRA(G,w',u) % izračuna d'(u,v) za vse v iz V(G)
end for
for vsak v in u iz V(G) do
  d(u,v} = d'(u,v) + h(v) - h(u)
end for
return D

Če je v Dijkstrovem algoritmu vrsta s prednostjo predstavljena z minimalno kopico, je časovna zahtevnost Johnsonovega algoritma O(|V||E|log|V|).

Primer

Slika:Primer_johnsonovega_algoritma.pdf

Glej tudi

Viri

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein: Introduction to algorithms

Osebna orodja