Dijkstrův algoritmus (připomenutí) Základní předpoklad w : H → R+ (nezáporné délky hran) “Upravený“ algoritmus prohledávání do šířky Dijkstra(G,s,w) 1 InitPaths(G,s) 2 S:=∅; InitQueue(Q) 3 for každý uzel u∈U do Enqueue(Q,u) 4 while not EmptyQueue(Q) 5 do u:=ExtractMin(Q); S:=S∪{u} 6 for uzel v∈Adj[u] do Relax(u,v,w) 7
O(|U|) O(|U| . lg |U|) O(|H| . lg |U|)
Možné ještě O(|U| . lg |U| + |H|) nebo O(|U|**2) Dijkstrův algoritmus - odst. 6.2
TI 8 / 1
Důkaz správnosti Dijkstrova algoritmu Tvrzení: Při uzavření uzlu u (řádka 5 ... S:=S∪{u}) platí d[u] = d(s,u) D: sporem - nechť je d[u] > d(s,u) pro nějaký uzavřený uzel, mějme nejkratší cestu s → u, x je poslední uzavřený
uzavřené uzly S >= 0
u
y s x
d[y] = d(s,y) ≤ d(s,u) < d[u] spor s vybráním uzlu u, když byl k dispozici uzel y s menší hodnotou TI 8 / 2
Bellmanův-Fordův algoritmus ? Co dělat v případě záporně ohodnocených hran ? Bellman-Ford(G,s,w) 1 InitPaths(G,s) 2 for i:=1 to |U|-1 do 3 for každou hranu (u,v)∈H do Relax(u,v,w) 4 for každou hranu (u,v)∈H 5 do if d[v] > d[u] + w(u,v) then return false 6 return true Složitost
O(|U| . |H|)
? Proč má nyní Relax konstantní časovou složitost ? Bellman-Ford algoritmus - odst. 6.3
TI 8 / 3
? Nelze B-F algoritmus nějak upravit / zrychlit ? Co když zavedeme frontu uzlů s úspěšným Relax a bereme jen hrany vycházející z těchto uzlů? • ukončení - při vyprázdnění fronty • problém - co když se fronta nevyprázdní? • v nejhorším případě zase O(|U| . |H|) Nejkratší cesty pro acyklické grafy 1 Topologicky uspořádáme uzly grafu G 2 InitPaths(G,s) 3 for každý uzel u v pořadí podle topologického uspořádání 4 do for každé v∈Adj[u] 5 do Relax(u,v,w) ?? Složitost ?? Bellman-Ford algoritmus - odst. 6.3
TI 8 / 4
Nejkratší cesty mezi všemi páry uzlů Označme |U| = n n x Dijkstra .....
O(n2 . lg n + n . |H|) Fib. halda O(|H| . n . lg n) binární halda O(n3) sekvenční fronta
Ale POZOR - jen pro nezáporné ohodnocení, jinak n x Bellman-Ford ... O(n2 . |H|) ~ O(n4) !? ? Jde to lépe ?
Kap. 7
ANO
TI 8 / 5
Nejkratší cesty a násobení matic Graf G reprezentujeme maticí w-délek W (vychází z matice sousednosti V a zahrnuje současně délky hran w): 0 pro i = j wij
w(ui, uj), i≠j, (ui,uj) ∈ H
=
∞ jinak matice w-vzdáleností D = [ dij ] : dij = dw(ui,uj) matice předchůdců P = [ pij ] pij
=
nil ... i=j nebo neexistuje cesta ui → uj, uk ... uk je předchůdce uj na cestě ui → uj
Cesty a násobení matic - odst. 7.1
TI 8 / 6
Cesty s omezeným počtem hran Předpoklad: nemáme záporné cykly! Nechť P je cesta ui → uj, která je tvořena max. m hranami a je nejkratší (podle w-délky) ≤ m hran
ui
uj P
P'
≤ m-1 hran
wkj
w(P) = w(P') + wkj (cesty tvořené m hranami vzniknou prodloužením cest o m-1 hranách)
uk
Cesty a násobení matic - odst. 7.1
TI 8 / 7
dij(m) ... w-délka cesty P dij(0) = 0 pro i=j ∞ jinak Pro m=1, 2, ..., n-1 máme formuli dij(m)
= min (dij(m-1), min (dik(m-1) + wkj)) přes všechna k = min (dik(m-1) + wkj) přes všechna k (wjj = 0) Operace "přinásobování" maticí W: D'' := D' . W 1 for i:=1 to n do 2 for j:=1 to n do 3 x:= ∞; 4 for k:=1 to n do x := min (x, d'[i,k] + w[k,j]) 5 d''[i,j] := x Cesty a násobení matic - odst. 7.1
TI 8 / 8
Nyní pronásobení použijeme D(1) = D(0).W, D(2) = D(1).W = W2, ..., D(n-1) = Wn-1 ? Složitost ? O(n4) ? Můžeme násobení zrychlit ? D(1) = W, D(2) = W2, D(4) = W4, ..., W2**k D(2) = W2, k= horní celá část lg(n-1), tedy složitost O(n3 . lg n) ?A co paměťová složitost?
Cesty a násobení matic - odst. 7.1
TI 8 / 9
Algoritmus Floyd-Warshall Cesta P : ui → uj s vnitřními uzly z {u1, u2, ..., uk} dij(k) - délka minimální cesty P {u1, u2, ..., uk-1} uj
ui
dij(0) = wij,
uk
dij(k) = min (dij(k-1) , dik(k-1) + dkj(k-1)) Floyd-Marshall - odst. 7.2
dij(n) = dij TI 8 / 10
Algoritmus Floyda-Warshala 1 D(0) := W 2 for k:=1 to n do 3 for i:=1 to n do 4 for j:=1 to n do 5
dij(k) := min (dij(k-1) , dik(k-1) + dkj(k-1))
6 return D(n) !!! Složitost
O(n3) !!! ? A co paměť ?
? A co, když chceme znát cesty, ne jen vzdálenosti ? Floyd-Marshall - odst. 7.2
TI 8 / 11
Výpočet matice předchůdců: pij(0)
pij(k)
=
=
nil
pro i=j nebo wij= ∞
i
jinak (tedy (ui,uj) ∈ H)
pij(k-1)
dij(k-1) ≤ dik(k-1) + dkj(k-1)
pkj(k-1)
dij(k-1) > dik(k-1) + dkj(k-1)
Reflexivně-tranzitivní uzávěr grafu (relace) W=V+E dij(k) = dij(k-1) ∨ (dik(k-1) ∧ dkj(k-1))
Floyd-Marshall - odst. 7.2
TI 8 / 12
Johnsonův aloritmus Pro řídké grafy ( |H| < O(n2)) je O(|H|.n) lepší než O(n3) Idea: n x Dijkstra, ale co s w(h) < 0 ?? Přehodnocení w → w' takové, že • pro každé u,v je minimální cesta podle w' minimální také podle w • w'(u,v) ≥ 0
Johnson - odst. 7.3
TI 8 / 13
Úprava G na G': • přidáme uzel U' = U ∪ {s} a hrany H = H ∪ {(s,u): u ∈ U}, w(h) = 0 pro nové hrany 0
s
v 0 u 0 0
• položíme h(u)=d(s,u) ... platí h(v) ≤ h(u) + w(u,v), tedy w'(u,v) = w(u,v) + h(u) - h(v) ≥ 0 !!! Johnson - odst. 7.3
TI 8 / 14
Johnsonův algoritmus 1 G → G' 2 Bellman-Ford(G',w,s) pokud false STOP ... O(n . |H|) 3 for každý uzel u∈U do h(u):=d(s,u) 4 for každou hranu (u,v)∈H do w'(u,v):=w(u,v)+h(u)-h(v) 5 for každý uzel u∈U n . O(n . lg n + |H|) Fib. heap 6 7
do Dijkstra(G, w', u) for každý uzel v∈U do d(u,v) := d'(u,v)-h(u)+h(v)
O(n . |H| . lg n) pro binární heap
Johnson - odst. 7.3
TI 8 / 15
Příklad: -2
0 0 0
-2 -2/0 0
3/1 3 2/3 2
33/1
3 3/3
0
4 4/4
s
6/7 6
4/4 4
1 1/0 0 0 -1
-1 -1/0
h(u) = min (0, délka nejkratší cesty s → u) w'(u,v) = w(u,v) + h(u) - h(v) Johnson - odst. 7.3
0
Dále
TI 8 / 16
Algebraické souvislosti Floyd-Marshall: dij(k) = min (dij(k-1) , dik(k-1) + dkj(k-1)) dvojoperace min, + označíme ⊕, ⊗ ⊗ efekt složení dvou spojení u → v ⊗ v → x ⊕ efekt kombinování alternativních spojení u
v⊕
?Jaké vlastnosti musí tyto operace mít, aby to fungovalo? Algebraické souvislosti - odst. 7.4
TI 8 / 17
Polookruh P = 〈P, ⊕, ⊗, 0, 1〉 : a ⊕ (b ⊕ c) = (a ⊕ b) ⊕ c a⊕0=0⊕a=a a⊕b=b⊕a a⊕a=a
〈P, ⊕, 0〉 je komutativní monoid idempotence
a ⊗ (b ⊗ c) = (a ⊗ b) ⊗ c a⊗1=1⊗a=a a⊗0=0⊗a=0
〈P, ⊗, 1〉 je monoid s nulovým prvkem
a ⊗ (b ⊕ c) = (a ⊗ b) ⊕ (a ⊗ c) (b ⊕ c) ⊗ a = (b ⊗ a) ⊕ (c ⊗ a)
distributivnost zleva a zprava
Algebraické souvislosti - odst. 7.4
TI 8 / 18
Uzavřený polookruh: a1 ⊕ a2 ⊕ a3 ⊕ ... je definováno pro lib. a1, a2, a3, ... a je • asociativní, komutativní, idempotentní a navíc • distributivní vůči ⊗ Kdy máme ∞ mnoho spojení? Když máme cykly! Uzávěr c* = 1 ⊕ c ⊕ (c ⊗ c) ⊕ (c ⊗ c ⊗ c) ... 0* = 1,
c ⊗ c* = c* ⊗ c,
c* = 1 ⊕ (c* ⊗ c), ...
Příklady polookruhů 〈R+ ∪{∞}, min, +, ∞, 0〉 a* = min (0, a, a+a, a+a+a, ...) = 0 〈R ∪{∞, -∞}, min, +, ∞, 0〉 Algebraické souvislosti - odst. 7.4
a* = 0 nebo -∞ TI 8 / 19
