Dijkstrov algoritem/METARAM

Iz MaFiRaWiki

Dijkstrov algoritem se uporablja predvsem na usmerjenih grafih. Povezave so ponavadi obtežene z neko utežjo - ceno. Kot smo že povedali, bomo iskali najkrajše poti iz enega vozlišča do vseh ostalih. Ker je vsaka najkrajša pot brez ciklov, je tudi združitev vseh najkrajših poti v en graf brez ciklov (druače vsaj ena izmed poti ne bi bila najkrajša). Ker že poznamo drevesa vemo, da združitev najkrajših poti zgradi vpeto drevo. Dijkstrov algoritem gradi vpeto drevo od začetnega vozlišča a, ki je koren vpetega drevesa, proti listom. Drevo zgradi tako, da vsakič doda iz množice vozlišč, ki še niso v drevesu, vozlišče v, ki ima najkrajšo pot od začetnega vozlišča.

Potek:

Imejmo graf G=<V,E> in naj bo cena povezave d(u,v) med vozliščema v0 in v večja ali enaka 0 za vsako povezavo iz množice E.
Poiščimo najkrajšo pot od začetnega vozlišča s do vseh ostalih vozlišč v iz V.

  • Postavimo števec i = 0 in si izberimo začetno vozlišče u0. Množica vozlišč vpetega drevesa je sedaj S0 = {u0 = s}, pot P(u0) = 0 in P(v) = neskončna, kjer je v<>u0.
    Če graf vsebue le eno vozlišče smo končali. Drugače nadaljujmo z drugim korakom.
  • Za vsak v iz V\Si zamenjamo neskončne poti z minimalno potjo min{P(v), P(ui)+ d(v,ui)}.
  • Poišči vozlišče v, ki je minimalno in naj bo to ui+1.
  • Naj bo sedaj Si+1 = Si unija {ui+1}
  • Povečaj števec i = i+1. Ko je Si = V končaj, drugače pojdi na drugi korak.
Osebna orodja