Bài giảng Phân tích thiết kế giải thuật - Chương 10: Các đường đi ngắn nhất từ một đỉnh nguồn (Single-Source Shortest Paths)
Single-Source Shortest Paths
Caùc ñöôøng ñi ngaén nhaát töø moät ñænh nguoàn
ª Baøi toaùn caùc ñöôøng ñi ngaén nhaát: moät soá thuaät ngöõ.
Cho moät ñoà thò coù troïng soá, coù höôùng G = (V, E), vôùi moät haøm troïng
soá w : E →
– Troïng soá cuûa moät ñöôøng ñi p = v0 , v1,…, vk
w(p) = i = 1…k w(vi− 1 , vi )
– Troïng soá cuûa ñöôøng ñi ngaén nhaát (shortest path weight) töø u ñeán v
p
min{w(p) : u v }
neáu coù ñöôøng ñi töø u ñeán v
d(u, v) =
caùc tröôøng hôïp khaùc
– Ñöôøng ñi ngaén nhaát töø u ñeán v laø baát kyø ñöôøng ñi p naøo töø u ñeán v
sao cho w(p) = d(u, v).
t
v
6
3
5
u
2
1 4
2
7
3
6
20.11.2004
2
x
y
Caùc ñöôøng ñi ngaén nhaát töø moät ñænh nguoàn (tieáp)
ª Baøi toaùn caùc ñöôøng ñi ngaén nhaát töø moät nguoàn duy nhaát (Single-
source shortest-paths problem):
– Cho ñoà thò G = (V, E) vaø moät ñænh nguoàn s V.
– Tìm ñöôøng ñi ngaén nhaát töø s ñeán moïi ñænh v V.
6
3
s
2
1 4
2
7
3
5
6
20.11.2004
Ch. 10: Single-Source Shortest Paths
3
Caïnh coù troïng soá aâm
ª Giaû thieát: Troïng soá cuûa caïnh coù theå aâm
– Chu trình coù theå coù troïng soá aâm
– Neáu toàn taïi moät chu trình coù troïng soá aâm ñeán ñöôïc (reachable) töø
s thì troïng soá cuûa ñöôøng ñi ngaén nhaát khoâng ñöôïc ñònh nghóa:
khoâng ñöôøng ñi naøo töø s ñeán moät ñænh naèm treân chu trình coù theå laø
ñöôøng ñi ngaén nhaát.
−4
3
−1
b
h
i
a
2
4
3
2
g
s
0
c
5
6
d
11
8
5
−
3
−8
−3
j
7
3
e
f
−
−
−6
soá trong moãi ñænh laø troïng soá ñöôøng ñi ngaén nhaát
töø ñænh nguoàn s.
20.11.2004
Ch. 10: Single-Source Shortest Paths
4
Caïnh coù troïng soá aâm (tieáp)
– Neáu toàn taïi moät chu trình coù troïng soá aâm treân moät ñöôøng ñi töø s
ñeán v, ta ñònh nghóa d(s, v) = − .
– Trong ví duï sau, caùc ñænh h, i, j khoâng ñeán ñöôïc töø s neân coù troïng
soá ñöôøng ñi ngaén nhaát laø (chöù khoâng laø − maëc duø chuùng naèm
treân moät chu trình coù troïng soá aâm).
b
a
3
−4
−1
h
i
2
4
3
2
s
0
g
−
c
5
6
d
11
8
5
3
−8
−3
j
7
3
e
−
f
−
−6
20.11.2004
Ch. 10: Single-Source Shortest Paths
5
Bieåu dieãn caùc ñöôøng ñi ngaén nhaát
ª Ñoà thò G = (V, E )
– Vôùi moïi ñænh v, ñænh cha (predecessor) cuûa v laø moät ñænh khaùc hay
laø NIL.
Duy trì p[v], con troû ñeán ñænh cha. Duøng p ñeå suy ra ñöôøng ñi
ngaén nhaát töø s ñeán v.
– Ñoà thò con Gp = (Vp , Ep ) (predecessor subgraph)
Vp = {v V : p[v] NIL} {s}
Ep = {(p[v], v) E : v Vp − {s}}
v
p[v]
20.11.2004
Ch. 10: Single-Source Shortest Paths
6
Bieåu dieãn caùc ñöôøng ñi ngaén nhaát (tieáp)
ª Cho G = (V, E) laø moät ñoà thò coù höôùng, coù troïng soá;
G khoâng chöùa chu trình troïng soá aâm ñeán ñöôïc töø ñænh nguoàn s V.
Caây caùc ñöôøng ñi ngaén nhaát vôùi goác taïi s laø ñoà thò coù höôùng G’ = (V’,
E’), vôùi V’ V vaø E’ E sao cho
1. V’ laø taäp caùc ñænh ñeán ñöôïc (reachable) töø s trong G
2. G’ laø caây coù goác vôùi goác laø s
3. Vôùi moïi v V’, ñöôøng ñi ñôn duy nhaát töø s ñeán v laø ñöôøng ñi
ngaén nhaát töø s ñeán v trong G .
20.11.2004
Ch. 10: Single-Source Shortest Paths
7
Caây caùc ñöôøng ñi ngaén nhaát coù goác taïi ñænh nguoàn s
Ví duï: trong (b) vaø (c) laø hai caây caùc ñöôøng ñi ngaén nhaát coù goác taïi ñænh
nguoàn s cuûa ñoà thò trong (a)
u
v
u
v
6
6
3
9
3
9
3
5
3
5
s
0
s
0
2
1 4
2
7
2
1 4
2
7
3
3
5
x
11
y
5
x
11
y
6
6
u
v
(a)
(b)
6
3
9
3
s
0
2
1 4
2
7
3
5
5
x
11
y
(c)
6
20.11.2004
Ch. 10: Single-Source Shortest Paths
8
Caáu truùc cuûa ñöôøng ñi ngaén nhaát
ª Lemma 25.1 (Ñöôøng ñi con cuûa ñöôøng ñi ngaén nhaát cuõng laø ñöôøng
ñi ngaén nhaát)
Cho
– Ñoà thò coù troïng soá, coù höôùng G = (V, E) vôùi haøm troïng soá
w : E →
– p = v1 , v2 ,…, vk ñöôøng ñi ngaén nhaát töø v1 ñeán vk
– Vôùi moïi i, j maø 1 i j k, goïi pij = vi , vi + 1 ,…, vj laø ñöôøng ñi
con (subpath) cuûa p töø vi ñeán vj .
pij laø moät ñöôøng ñi ngaén nhaát töø vi ñeán vj .
vk
pjk
vj
p1i
v1
pij
vi
20.11.2004
Ch. 10: Single-Source Shortest Paths
9
Caáu truùc cuûa ñöôøng ñi ngaén nhaát (tieáp)
Chöùng minh
Phaûn chöùng.
p’ij
vk
pjk
vj
p1i
v1
pij
vi
20.11.2004
Ch. 10: Single-Source Shortest Paths
10
Caáu truùc cuûa ñöôøng ñi ngaén nhaát (tieáp)
ª Heä luaän 25.2
Cho
– Ñoà thò coù troïng soá, coù höôùng G = (V, E) vôùi haøm troïng soá
w : E →
– p laø ñöôøng ñi ngaén nhaát töø s ñeán v, vaø coù theå ñöôïc phaân thaønh
p’
s u → v.
Troïng soá cuûa ñöôøng ñi ngaén nhaát töø s ñeán v laø
d(s, v) = d(s, u) + w(u, v).
v
p’
u
s
20.11.2004
Ch. 10: Single-Source Shortest Paths
11
Caáu truùc cuûa ñöôøng ñi ngaén nhaát (tieáp)
Chöùng minh
v
p’
u
s
20.11.2004
Ch. 10: Single-Source Shortest Paths
12
Caáu truùc cuûa ñöôøng ñi ngaén nhaát (tieáp)
ª Lemma 25.3
Cho
– Ñoà thò coù troïng soá, coù höôùng G = (V, E) vôùi haøm troïng soá
w : E →
– Ñænh nguoàn s
Vôùi moïi caïnh (u, v) E, ta coù d(s, v) d(s, u) + w(u, v).
v
u
s
20.11.2004
Ch. 10: Single-Source Shortest Paths
13
Kyõ thuaät nôùi loûng
ª Kyõ thuaät nôùi loûng (relaxation)
– Duy trì cho moãi ñænh v moät thuoäc tính d[v] duøng laøm chaän treân cho
troïng soá cuûa moät ñöôøng ñi ngaén nhaát töø s ñeán v.
– bieán d[v] ñöôïc goïi laø öôùc löôïng ñöôøng ñi ngaén nhaát (shortest path
estimate)
– Khôûi ñoäng caùc öôùc löôïng ñöôøng ñi ngaén nhaát vaø caùc predecessors
baèng thuû tuïc sau
INITIALIZE-SINGLE-SOURCE(G, s)
1 for each vertex v V[G]
2
3
do d[v]
p[v] NIL
4 d[s] 0
20.11.2004
Ch. 10: Single-Source Shortest Paths
14
Kyõ thuaät nôùi loûng (tieáp)
ª Thöïc thi nôùi loûng leân moät caïnh (u, v): kieåm tra xem moät ñöôøng ñi ñeán
v thoâng qua caïnh (u, v) coù ngaén hôn moät ñöôøng ñi ñeán v ñaõ tìm ñöôïc
hieän thôøi hay khoâng. Neáu ngaén hôn thì caäp nhaät d[v] vaø p[v].
s
0
2
5
9
u
v
RELAX(u, v, w)
1 if d[v] d[u] + w(u, v)
2
3
then d[v] d[u] + w(u, v)
p[v] u
20.11.2004
Ch. 10: Single-Source Shortest Paths
15
Thöïc thi nôùi loûng leân moät caïnh
u
v
u
v
2
2
5
9
5
6
RELAX(u, v, w)
RELAX(u, v, w)
u
v
u
v
2
2
5
7
5
6
(a)
(b)
Trò cuûa d[v] giaûm sau khi
goïi RELAX(u, v, w)
Trò cuûa d[v] khoâng thay ñoåi sau khi
goïi RELAX(u, v, w)
20.11.2004
Ch. 10: Single-Source Shortest Paths
16
Kyõ thuaät nôùi loûng (tieáp)
ª Caùc giaûi thuaät trong chöông naøy goïi INITIALIZE-SINGLE-SOURCE vaø
sau ñoù goïi RELAX moät soá laàn ñeå nôùi loûng caùc caïnh.
– Nôùi loûng laø caùch duy nhaát ñöôïc duøng ñeå thay ñoåi caùc öôùc löôïng
ñöôøng ñi ngaén nhaát vaø caùc predecessors.
– Caùc giaûi thuaät khaùc nhau ôû thöù töï vaø soá laàn goïi RELAX leân caùc
caïnh.
20.11.2004
Ch. 10: Single-Source Shortest Paths
17
Caùc tính chaát cuûa kyû thuaät nôùi loûng
ª Lemma 25.4
Cho
– Ñoà thò coù troïng soá, coù höôùng G = (V, E )ø, vôùi haøm troïng soá
w : E →
– Caïnh (u, v) E.
Ngay sau khi goïi RELAX(u, v, w) ta coù
d[v] d[u] + w(u, v) .
20.11.2004
Ch. 10: Single-Source Shortest Paths
18
Caùc tính chaát cuûa kyû thuaät nôùi loûng (tieáp)
ª Lemma 25.5
Cho
– Ñoà thò coù troïng soá, coù höôùng G = (V, E)ø, vôùi haøm troïng soá
w : E →
– Ñænh nguoàn s.
– G ñöôïc khôûi ñoäng bôûi INITIALIZE-SINGLE-SOURCE(G, s).
– Vôùi moïi v V, d[v] d(s, v), baát bieán naøy ñöôïc duy trì ñoái vôùi
moïi daõy caùc böôùc nôùi loûng leân caùc caïnh cuûa G
– Moät khi d[v] ñaït ñeán caän döôùi d(s, v) cuûa noù thì noù seõ khoâng bao
giôø thay ñoãi.
20.11.2004
Ch. 10: Single-Source Shortest Paths
19
Caùc tính chaát cuûa kyû thuaät nôùi loûng (tieáp)
ª Heä luaän 25.6
Cho
– Ñoà thò coù troïng soá, coù höôùng G = (V, E)ø, vôùi haøm troïng soá
w : E →
– Ñænh nguoàn s
– Khoâng coù ñöôøng ñi töø s ñeán moät ñænh v V.
Sau khi G ñöôïc khôûi ñoäng bôûi INITIALIZE-SINGLE-SOURCE(G, s), ta coù
– ñaúng thöùc d[v] = d(s, v)
– ñaúng thöùc naøy ñöôïc duy trì thaønh baát bieán ñoái vôùi moïi daõy caùc
böôùc nôùi loûng leân caùc caïnh cuûa G.
20.11.2004
Ch. 10: Single-Source Shortest Paths
20
Tải về để xem bản đầy đủ
45 trang
09/05/2022
2400
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Phân tích thiết kế giải thuật - Chương 10: Các đường đi ngắn nhất từ một đỉnh nguồn (Single-Source Shortest Paths)", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- bai_giang_phan_tich_thiet_ke_giai_thuat_chuong_10_cac_duong.ppt
