Bài giảng Phân tích thiết kế giải thuật - Chương 10: Single - Source shortest paths

ap 
Tạo heap tốn O ( V ) thời gian. 
Mỗi E XTRACT -M IN tốn O (lg V ) thời gian, vậy tất cả các E XTRACT -M IN tốn O ( V lg V ) 
Tất cả các lần gọi R ELAX tốn O ( E lg V ) thời gian, vì mỗi D ECREASE -K EY để hiện thực R ELAX tốn O (lg V ) thời gian 
Thời gian chạy tổng cộng: O (( V + E ) lg V ). 
20.11.2004 
26 
Ch. 10: Single-Source Shortest Paths 
Phân tích giải thuật của Dijkstra 
(tiếp) 
Fibonacci heap 
Tạo heap với  V  phần tử tốn O ( V ) thời gian. 
Mỗi E XTRACT -M IN tốn O (lg V ) phí tổn bù trừ, vậy tất cả các E XTRACT -M IN tốn O ( V lg V ) thời gian 
Tất cả các lần gọi R ELAX tốn O ( E ) thời gian, vì mỗi D ECREASE -K EY để hiện thực R ELAX tốn O (1) phí tổn bù trừ 
Thời gian chạy tổng cộng: O ( V lg V + E ). 
20.11.2004 
27 
Ch. 10: Single-Source Shortest Paths 
Thực thi giải thuật của Dijkstra 
 
 
 
 
0 
10 
1 
6 
4 
9 
7 
2 
2 
5 
3 
u 
v 
x 
y 
s 
(a) 
10 
 
 
5 
0 
10 
1 
6 
4 
9 
7 
2 
2 
5 
3 
u 
v 
x 
y 
s 
(b) 
Đỉnh màu đen là đỉnh trong S 
Đỉnh màu xám là đỉnh được đem vào S trong lần lặp tới 
Ngay trước khi vào vòng lặp while: 
Vòng while: ngay sau lần lặp 1 
20.11.2004 
28 
Ch. 10: Single-Source Shortest Paths 
Thực thi giải thuật của Dijkstra (tiếp) 
8 
14 
7 
5 
0 
10 
1 
6 
4 
9 
7 
2 
2 
5 
3 
u 
v 
x 
y 
s 
(c) 
8 
13 
7 
5 
0 
10 
1 
6 
4 
9 
7 
2 
2 
5 
3 
u 
v 
x 
y 
s 
(d) 
Vòng while: ngay sau lần lặp 2 
Vòng while: ngay sau lần lặp 3 
20.11.2004 
29 
Ch. 10: Single-Source Shortest Paths 
Thực thi giải thuật của Dijkstra (tiếp) 
8 
9 
7 
5 
0 
10 
1 
6 
4 
9 
7 
2 
2 
5 
3 
u 
v 
x 
y 
s 
(e) 
8 
9 
7 
5 
0 
10 
1 
6 
4 
9 
7 
2 
2 
5 
3 
u 
v 
x 
y 
s 
(f) 
Vòng while: ngay sau lần lặp 4 
Vòng while: ngay sau lần lặp 5 
20.11.2004 
30 
Ch. 10: Single-Source Shortest Paths 
Tính đúng đắn của giải thuật của Dijkstra 
Định lý 25.10 (Tính đúng đắn của giải thuật của Dijkstra) 
Thực thi giải thuật của Dijkstra lên đồ thị G = ( V , E ) có trọng số và có hướng với 
hàm trọng số w : E   không âm 
đỉnh nguồn s . 
 
Khi giải thuật thực thi xong, 
	 d [ u ] = d ( s , u )	cho mọi đỉnh u  V . 
Chứng minh 
Sẽ chứng minh:  u  V , d [ u ] = d ( s , u ) khi u được đưa vào tập S và sau đó đẳng thức luôn được duy trì. 
20.11.2004 
31 
Ch. 10: Single-Source Shortest Paths 
Tính đúng đắn của giải thuật của Dijkstra 
Chứng minh (tiếp) 
Chứng minh bằng phản chứng. 
( * ) Gọi u là đỉnh đầu tiên sao cho d [ u ]  d ( s , u ) khi u được đưa vào 	tập S . 
Phải có một đường đi từ s đến u . Vì nếu không thì d ( s , u ) = , do đó d [ u ] = , do đó d [ u ] = d ( s , u ) dùng Hệ luận 25.6, mâu thuẫn! 
Do đó có đường đi ngắn nhất p từ s đến u , với s  S và u  V  S . Gọi y là đỉnh đầu tiên trên p sao cho y  V  S . Đặt x = p [ y ]. 
s 
x 
y 
u 
p 1 
p 2 
S 
20.11.2004 
32 
Ch. 10: Single-Source Shortest Paths 
Tính đúng đắn của giải thuật của Dijkstra 
Chứng minh (tiếp) 
Chứng tỏ d [ y ] = d ( s , y ) khi u được đưa vào tập S : theo ( * ) ta phải có d [ x ] = d ( s , x ) khi x được đưa vào S . Khi đó cạnh ( x , y ) được nới lỏng nên d [ y ] = d ( s , y ) dùng Lemma 25.7. 
Vì y trước u trên đường đi ngắn nhất từ s đến u và mọi trọng số đều dương nên d ( s , y )  d ( s , u ). 
d [ y ] = d ( s , y ) 
  d ( s , u ) 
  d [ u ]	dùng Lemma 25.5. 
s 
x 
y 
u 
p 1 
p 2 
S 
20.11.2004 
33 
Ch. 10: Single-Source Shortest Paths 
Tính đúng đắn của giải thuật của Dijkstra 
Chứng minh (tiếp) 
Khi u được chọn bởi E XTRACT -M IN thì y cũng còn trong Q nên d [ u ]  d [ y ], do đó bất đẳng thức : 
d [ y ] = d ( s , y ) = d ( s , u ) = d [ u ], từ đó d [ u ] = d ( s , u ), mâu thuẫn với ( * )! 
Dùng Lemma 25.5 để chứng minh phần còn lại. 
20.11.2004 
34 
Ch. 10: Single-Source Shortest Paths 
Tính đúng đắn của giải thuật của Dijkstra (tiếp) 
Hệ luận 25.11 
Thực thi giải thuật của Dijkstra lên đồ thị G = ( V , E ) có trọng số và có hướng với 
hàm trọng số w : E   không âm 
đỉnh nguồn s . 
 
Khi giải thuật thực thi xong thì đồ thị G p là cây các đường đi ngắn nhất có gốc tại s . 
20.11.2004 
35 
Ch. 10: Single-Source Shortest Paths 
Giải thuật của Bellman-Ford 
 Cho G = ( V , E ) là đồ thị có trọng số, có hướng 
Hàm trọng số w : E   
Đỉnh nguồn s . 
B ELLMAN -F ORD ( G , w , s ) 
1 I NITIALIZE -S INGLE -S OURCE ( G , s ) 
2 for i  1 to | V [ G ] | - 1 
3 do for each edge ( u , v )  E [ G ] 
4 do R ELAX ( u , v , w ) 
5 for each edge ( u , v )  E [ G ] 
6 do if d [ v ] > d [ u ] + w ( u , v ) 
7 then return FALSE 
8 return TRUE 
20.11.2004 
36 
Ch. 10: Single-Source Shortest Paths 
Phân tích giải thuật của Bellman-Ford 
Thời gian chạy: 
Khởi tạo: ( V ) thời gian 
 | V | - 1 lượt, mỗi lượt O ( E ) thời gian 
vòng lặp for dòng 5-7: O ( E ) thời gian 
Thời gian chạy tổng cộng: O ( V E ) 
20.11.2004 
37 
Ch. 10: Single-Source Shortest Paths 
Thực thi giải thuật Bellman-Ford 
 
 
 
 
0 
6 
5 
7 
9 
8 
7 
u 
v 
x 
y 
z 
(a) 
 2 
 3 
 4 
2 
6 
 
 
7 
0 
6 
5 
7 
9 
8 
7 
u 
v 
x 
y 
z 
(b) 
 2 
 3 
 4 
2 
Trong mỗi lượt, thứ tự relax các cạnh là: 
( u , v ) ( u , x ) ( u , y ) ( v , u ) ( x , v ) (x , y ) ( y , v ) ( y , z ) ( z , u ) ( z , x ) 
Ngay trước lượt đầu: 
Ngay sau lượt đầu: 
Cạnh ( u , v ) được sơn xám nếu [ v ] = u 
20.11.2004 
38 
Ch. 10: Single-Source Shortest Paths 
Thực thi giải thuật Bellman-Ford (tiếp) 
2 
4 
2 
7 
0 
6 
5 
7 
9 
8 
7 
u 
v 
x 
y 
z 
(d) 
 2 
 3 
 4 
2 
2 
4 
 2 
7 
0 
6 
5 
7 
9 
8 
7 
u 
v 
x 
y 
z 
(e) 
 2 
 3 
 4 
2 
6 
4 
2 
7 
0 
6 
5 
7 
9 
8 
7 
u 
v 
x 
y 
z 
(c) 
 2 
 3 
 4 
2 
Ngay sau lượt 2: 
Ngay sau lượt 3: 
Ngay sau lượt 4: 
20.11.2004 
39 
Ch. 10: Single-Source Shortest Paths 
Tính đúng đắn của giải thuật Bellman-Ford 
Lemma 25.12 
Cho 
Đồ thị có trọng số và có hướng G = ( V , E ), với hàm trọng số 
w : E   
Đỉnh nguồn s 
G không chứa các chu trình có trọng số âm có thể đến được từ s . 
 
Khi giải thuật B ELLMAN -F ORD thực thi xong thì d [ v ] = d ( s , v ) cho mọi đỉnh v đến được từ s . 
20.11.2004 
40 
Ch. 10: Single-Source Shortest Paths 
Tính đúng đắn của giải thuật Bellman-Ford (tiếp) 
Chứng minh 
Gọi v là một đỉnh đến được từ s . Gọi p = là một đường đi ngắn nhất từ s đến v . Vì p là đường đi đơn nên k  | V | - 1. 
Sẽ chứng minh: d [ v i ] = ( s , v i ) sau lượt nới lỏng thứ i , với i = 0,..., k , và đẳng thức được duy trì sau đó. 
Dùng quy nạp: 
Cơ bản: d [ v 0 ] = ( s , v 0 ) = 0	(vì v 0 = s ) 
Giả thiết quy nạp: d [ v i - 1 ] = ( s , v i - 1 ) sau lượt nới lỏng thứ i - 1 . 
Bước quy nạp: Cạnh ( v i - 1 , v i ) được nới lỏng trong lượt thứ i nên 
d [ v i ] = ( s , v i ) sau lượt i và tại mọi thời điểm sau đó, theo Lemma 25.7. 
Để ý là k  | V | - 1 và có | V | - 1 lượt nới lỏng. 
20.11.2004 
41 
Ch. 10: Single-Source Shortest Paths 
Tính đúng đắn của giải thuật Bellman-Ford (tiếp) 
Hệ luận 25.13 
Cho 
Đồ thị có trọng số và có hướng G = ( V , E ), với hàm trọng số 
w : E   
Đỉnh nguồn s 
 
Với mọi đỉnh v  V , tồn tại đường đi từ s đến v nếu và chỉ nếu B ELLMAN -F ORD hoàn tất với d [ v ]   khi nó thực thi trên G . 
20.11.2004 
42 
Ch. 10: Single-Source Shortest Paths 
Tính đúng đắn của giải thuật của Bellman-Ford (tiếp) 
Định lý 25.14 (Tính đúng đắn của giải thuật của Bellman-Ford) 
Thực thi B ELLMAN -F ORD lên đồ thị G = ( V , E ) có trọng số và có hướng với 
hàm trọng số w : E   
đỉnh nguồn s 
 
(i) Nếu G không chứa chu trình có trọng số âm đến được từ s , thì 
(1) giải thuật trả về TRUE . 
(2) d [ v ] = d ( s , v ) cho mọi đỉnh v  V 
(3) đồ thị G p là cây các đường đi ngắn nhất có gốc tại s . 
(ii) Nếu G chứa một chu trình có trọng số âm đến được từ s , thì giải 
thuật trả về FALSE . 
20.11.2004 
43 
Ch. 10: Single-Source Shortest Paths 
Tính đúng đắn của giải thuật của Bellman-Ford (tiếp) 
Chứng minh 
(i) Giả sử G không chứa chu trình có trọng số âm đến được từ s . 
Nếu v đến được từ s thì Lemma 25.12 chứng minh (2). 
Nếu v không đến được từ s thì có (2) từ Hệ luận 25.6 
Lemma 25.9 cùng với (2) chứng minh (3). 
Khi giải thuật hoàn tất, ta có với mọi cạnh ( u , v ): 
d [ v ] = d ( s , v )  d ( s , u ) + w ( u , v )	(từ Lemma 25.3) 
 = d [ u ] + w ( u , v ), 
vậy các test dòng 6 khiến giải thuật trả về TRUE , chứng minh (1). 
20.11.2004 
44 
Ch. 10: Single-Source Shortest Paths 
Tính đúng đắn của giải thuật của Bellman-Ford 
Chứng minh (tiếp) 
(ii) Giả sử G chứa một chu trình có trọng số âm đến được từ s là 
c =  v 0 ,, v k  với v 0 = v k 
Vậy	  i = 1 k w ( v i  1 , v i ) < 0	( * ) 
Chứng minh (ii) bằng phản chứng: 
Giả sử Bellman-Ford trả về TRUE , thì (dòng 5-8) 
d [ v i ]  d [ v i  1 ] + w ( v i  1 , v i ),	với i = 1,, k 
Từ trên, lấy tổng, 
 i = 1 k d [ v i ]   i = 1 k d [ v i  1 ] +  i = 1 k w ( v i  1 , v i )	 # 
Vì 
 i = 1 k d [ v i ] =  i = 1 k d [ v i  1 ], và 
d [ v i ] < 	(Hệ luận 25.13), nên cùng với # ta có 
0   i = 1 k w ( v i  1 , v i ),	mâu thuẫn với ( * )! 
v 0 , v k 
v 1 
v k - 1 
20.11.2004 
45 
Ch. 10: Single-Source Shortest Paths