From 82380dd596b0eab53fc521d22510137dc672b160 Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Mon, 28 May 2007 12:25:34 +0200 Subject: [PATCH 1/1] Drobne upravy dukazu Dijkstry. --- 10-cesty/10-cesty.tex | 15 +++++++++++++-- 1 file changed, 13 insertions(+), 2 deletions(-) diff --git a/10-cesty/10-cesty.tex b/10-cesty/10-cesty.tex index 54bdd80..805de67 100644 --- a/10-cesty/10-cesty.tex +++ b/10-cesty/10-cesty.tex @@ -139,10 +139,14 @@ Nyn Uká¾eme si trik pro ohodnocené hrany: hranu délky $l$ podrozdìlíme na $l$ hran délky 1 a pak spustíme BFS. Algoritmus pobì¾í s èasovou -slo¾itostí $O((m+n)l_{max})$. To není zrovna moc výhodné, a proto si uká¾eme tzv. {\I Budíkovou taktiku }: +slo¾itostí $O((m+n)l_{max})$. To není zrovna moc výhodné, a proto si uká¾eme tzv. {\I Budíkovou taktiku}: + +Místo toho, abychom ka¾dou hranu podrozdìlovali, si budeme pro ka¾dý vrchol pamatovat \uv{èas budíku} $b$. Èasem $b(v)$ budíku vrcholu~$v$ rozumíme èas, kdy se do tohoto vrcholu vlna dostane, kdy¾ se bude ¹íøit po dosud známých hranách. Na zaèátku nastavíme $\forall v \in V: b(v) = l(s,v)$ a pokud pøi bìhu algoritmu objevíme hranu, která nám umo¾ní dostat se do $v$ rychleji, tak hodnotu $b(v)$ zmìníme. +Algoritmus pak bude pracovat tak, ¾e bude spát, dokud nezazvoní nìjaký budík (co¾ znamená, ¾e +jsme dorazili do nìjakého vrcholu). Tato taktika nás pøivede k Dijkstrovu algoritmu, kde se ze dvoustavového $z(v)$ stane tøístavové $z(v)) \in \{{\bf{N}}, {\bf{V}}, {\bf{H}}\}$, kde {\bf{N}} znamená nevidìn, {\bf{V}} vidìn a {\bf{H}} hotov. Podle hodnoty $z(v)$ se @@ -168,7 +172,14 @@ pak $D(v)$ rovn najde nejkrat¹í cesty v èase $\O(n^2)$. \proof -na pøí¹tí pøedná¹ce +V prùbìhu algoritmu se maximálnì $n$-krát hledá vrchol $v$ s minimálním $D(v)$, +maximálnì $m$-krát se pøenastavuje $D(v)$. Pokud bude struktura $D$ ulo¾ena jako +pole (hledání minima v $\O(n)$, zmìna hodnoty $\O(1)$), bude celková +èasová slo¾itost Dijkstrova algoritmu $\O(n^2 + m) = \O(n^2)$. Fakt, ¾e se algoritmus +zastaví je evidentní, proto¾e se stav ¾ádného vrcholu nevrací z {\bf{H}} do {\bf{V}}. + +Úplný dùkaz správnosti a èasové slo¾itosti i pro hrany ohodnocené reálnými èísly +bude na pøí¹tí pøedná¹ce. \qed Nahlédnìme nyní, zda by vedlo k~vylep¹ení èasové slo¾itosti, kdybychom pøi~implementaci -- 2.39.5