TI 8.1
NEJKRATŠÍ CESTYMEZI VŠEMI UZLY
Nejkratší cesty - kap. 7
TI 8.2
Nejkratší cesty mezi všemi uzly
Seznámíme se s následujícími pojmy:
• matice w-délek, matice w-vzdáleností, matice předchůdců
• Floydův-Warshallův algoritmus
• Johnsonův algoritmus, přehodnocení hran
Skripta kap. 7, str. 123 – 138
Nejkratší cesty – kap. 7
TI 8.3
Jak zjistíme nejkratší cesty mezi všemi páry uzlů ?
Označme |U| = n
Pro nezáporné ohodnocení hran lze uvažovat
O(n2 . lg n + n . |H|) Fibonacci-ho halda
n x Dijkstra ... O(|H| . n . lg n) binární halda
O(n3) fronta jako sekvenční seznam
A pro záporné ohodnocení hran n x Bellman-Ford ... O(n2 . |H|) ~ O(n4) !?
? Jde to lépe ? ANO !
Nejkratší cesty - kap. 7
TI 8.4
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
Cesty a matice - odst. 7.1
Výsledky získáme ve formě
matice w-vzdáleností D = [ dij ] : dij = dw(ui,uj)
Doplňující informace o samotných cestách ukládáme do
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
TI 8.5
Algoritmus Floyda-Warshalla
Floyd-Warshall - odst. 7.2
Základní myšlenka:
postupně rozšiřujeme povolené vnitřní uzly minimálních cest:
, {u1}, {u1, u2},..., {u1, u2, ..., uk},..., {u1, u2, ..., un}
cesta P : ui uj s vnitřními uzly z {u1, u2, ..., uk}
dij(k) - délka minimální cesty P
dij(0) = wij ui
uk
uj
{u1, u2, ..., uk-1}
dij(k) = min (dij
(k-1) , dik(k-1) + dkj
(k-1))
dij(n) = dij
TI 8.6
Algoritmus Floyda-Warshalla
1 D(0) W
2 for k 1 to n {
3 for i 1 to n {
4 for j 1 to n {
5 dij(k) min (dij
(k-1) , dik(k-1) + dkj
(k-1))
6 } } }
7 return D(n)
Floyd-Warshall - odst. 7.2
!!! Časová složitost : O(n3) !!!
? A co paměťová složitost ?
?A co, když chceme znát cesty, ne jen vzdálenosti ?
TI 8.7
Výpočet matice předchůdců:
pij(0) = nil pro i=j nebo wij=
i jinak (tedy pro (ui,uj) H)
pij(k) = pij
(k-1) pro dij(k-1) dik
(k-1) + dkj(k-1)
pkj(k-1) pro dij
(k-1) > dik(k-1) + dkj
(k-1)
Floyd-Warshall - odst. 7.2
Reflexivně-tranzitivní uzávěr grafu (relace)
W = V + E
dij(k) = dij
(k-1) (dik(k-1) dkj
(k-1))
TI 8.8
Kontrolní otázky
1. Podobně jako je při provádění Floyd-Warshallova algoritmu možné počítat matici P předchůdců uzlů na nejkratších cestách, je možné také počítat matici Q následníků uzlů na nejkratších cestách. Určete pravidlo, podle něhož se nastaví počáteční hodnoty prvků qij
(0) této matice, a pravidlo pro přechod od (k-1)-ní ke k-té iteraci hodnot qij.
2. Dalším rozšířením Floyd-Warshallova algoritmu zajistěte, aby po ukončení výpočtu byl znám počet hran na nejkratších cestách mezi všemi uzly (opět ve formě matice označené např. R). (Návod: Inspirujte se řešením obdobného problému pro algoritmus Dikstrův a Bellman-Fordův.)
3. Zdůvodněte, proč je provádění Floyd-Warshallova algoritmu možné všechny iterace matice D(k) uchovávat v jediném poli. (Návod: Ověřte, že vnitřní dva cykly nemění hodnotu prvků v k-tém řádku a k-tém sloupci, na nichž závisí hodnoty prvků v nové iteraci.)
4. Jak se při použití Floyd-Warshallova algoritmu zjistí případná existence záporných cyklů v grafu?
Nejkratší cesty – kap. 7
TI 8.9
Johnsonův aloritmus
Úvaha: (označíme |U|=n)Pro řídké grafy (|H|<<O(n2)) je O(|H|.n) lepší než O(n3)
takže O(n.(|H| + n.lg n)) je lepší než O(n3)
Idea: n x Dijkstra (+ Fib. heap), ale co s w(h) < 0 ??
Johnson - odst. 7.3
Přehodnocení w w' takové, že
• pro každé u,v je cesta u v minimální podle w' minimální také podle w
• w'(u,v) 0
TI 8.10
? Jak najít přehodnocení w' , které bude zachovávat minimálnost cest?
Johnson - odst. 7.3
V: Nechť je pro graf G = H, U s ohodnocením hran w: H R dána funkce h: U R. Nechť je ohodnocení w' pro každou hranu (u,v) dané vztahem
w'(u,v) = w(u,v)+h(u)-h(v)
Potom pro cestu L: u v platí, že L je minimální podle w, právě když je minimální podle w'.
D: platí w'(L) = w(L)+h(u)-h(v) cesta minimální pro w je minimální i pro w' a naopak
Zbývá nalézt vhodné h, aby bylo w'(u,v) 0 !!!
TI 8.11
Úprava G na G':• přidáme uzel s: U' = U {s}
a hrany H = H {(s,u): u U}, w(x) = 0 pro nové hrany x
0
0
0
0
v
u
Johnson - odst. 7.3
• položíme h(u)=d(s,u) ... platí h(v) h(u) + w(u,v), tedyw'(u,v) = w(u,v) + h(u) - h(v) 0 !!!
s
TI 8.12
Johnsonův algoritmus1 G G'2 Bellman-Ford(G',w,s) pokud false STOP 3 for každý uzel uU { h(u) d(s,u) }4 for každou hranu (u,v)H { 5 w'(u,v) w(u,v) + h(u) - h(v)6 for každý uzel uU {
7 Dijkstra(G, w', u)
8 for každý uzel vU {
9 d(u,v) d'(u,v) - h(u) + h(v)
10 }
11 }
Johnson - odst. 7.3
O(n.|H|)
O(n2.lg n + n.|H|)(pro Fib. heap)
O(n.|H|.lg n) pro binární heap
TI 8.13
0
-2
-1
0
0
-2/0 3/12/3 3/1
3/3
4/4
1/0
-1/0
6/74/4
h(u) = min (0, délka nejkratší cesty s u)
w'(u,v) = w(u,v) + h(u) - h(v)
Johnson - odst. 7.3
s
0
0
0
0
0
TI 8.14
Algebraické souvislosti
Floyd-Warshall:
dij(k) = min (dij
(k-1) , dik(k-1) + dkj
(k-1))
Algebraické souvislosti - odst. 7.4
dvojoperace min, +označíme ,
?Jaké vlastnosti musí tyto operace mít, aby to fungovalo?
efekt složení dvou spojení u v v x
efekt kombinování alternativních spojení u v
TI 8.15
Polookruh
PP = P, , , 0, 1 :
a (b c) = (a b) c P, , 0 a 0 = 0 a = a je komutativnía b = b a monoida a = a idempotence
a (b c) = (a b) c P, , 1 a 1 = 1 a = a je monoida 0 = 0 a = 0 s nulovým prvkem
a (b c) = (a b) (a c) distributivnost(b c) a = (b a) (c a) zleva a zprava
Algebraické souvislosti - odst. 7.4
Teď přijde trochu matematiky, podrobněji viz skripta ...
TI 8.16
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
Algebraické souvislosti - odst. 7.4
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 a* = 0 nebo - (pro a<0)
TI 8.17
Řešení obecné úlohy o spojeních
Máme jednoduchý OG G = H,U a ohodnocení
: H P , (h) 0, kde PP = P, , , 0, 1 je polookruh. Doplníme ohodnocení o
(u,v) = 0 pro (u,v) H.
Spojení L = u1,u2,...,uk ohodnotíme pomocí jeho hran
(L) = (u1,u2) (u2,u3) ... (uk-1,uk)
takže platí (L1 L2) = (L1) (L2)
(L1 L2 ... Lr) = (L1) (L2) ... (Lr)
Rozšíříme i na množiny spojení {Li}iI mezi stejnými uzly
({Li}iI) = iI (Li)
Algebraické souvislosti - odst. 7.4
TI 8.18
F-W algoritmus zobecníme, aby pro všechna u,v U počítal
suv = L : uv (L)
Předpokládáme U = {1,2, ...|U|}, L(i,j,k) - všechna spojení z i do j s vnitřními uzly pouze z množiny {1,2,...,k}.
Postupně se počítají
sij(k) = L L(i,j,k) (L)
pomocí rekurence
sij(k) = sij
(k-1) (sik(k-1) (skk
(k-1))* skj(k-1) )
a počátečního nastavení
sij(0) = (i,j) pro i j, sij
(0) = 1 (i,j) pro i=j
Algebraické souvislosti - odst. 7.4
Ta trocha matematiky pokračuje ...
TI 8.19
Zobecněný F-W algoritmus
Floyd-Warshall-G(G, )
1 for i1 to n {
2 for j 1 to n { sij(0) (i,j) }
3 sii(0) 1 (i,i)
4 }
5 for k 1 to n {
6 for i 1 to n {
7 for j 1 to n {
8 sij(k) sij
(k-1) (sik(k-1) (skk
(k-1))* skj(k-1) )
9 } } }
8 return S(n)
za co je tam ta 1 ???
Algebraické souvislosti - odst. 7.4
TI 8.20
Pro polookruhR+ {}, min, +, , 0 a* = min (0, a, a+a, a+a+a, ...) = 0 uzávěrový činitel (skk
(k-1))* odpadá
sij(k) = sij
(k-1) (sik(k-1) skj
(k-1) )
Pro polokruhR {, -}, min, +, , 0 a* = 0 nebo - (pro a<0) hodnota (skk
(k-1))* je - pokud spojení z u do v prochází
cyklem < 0
P = 0,1, max, . , 0, 1 a*=1 - nejspolehlivější spojení
P = Rk, max, min , rmin, rmax - spojení s maximální
propustností
Rk je konečná množina reálných čísel
Algebraické souvislosti - odst. 7.4
A tohle je několik výsledků ...
TI 8.21
Kontrolní otázky
1. Jak je třeba definovat operace a a nosič (tj. množinu P) v odpovídajícím polookruhu, aby zobecněný Floyd-Warshallův algoritmus určil počet různých spojení mezi jednotlivými dvojicemi uzlů.
Nejkratší cesty – kap. 7