Bài giảng Thiết kế và đánh giá thuật toán - Đường đi ngắn nhất - Lê Nguyên Khôi

Thiết Kế & Đánh Giá Thuật Toán
Đường Đi Ngắn Nhất
TS. Lê Nguyên Khôi
Trường Đại Học Công Nghệ - ĐHQGHN
Nội Dung

 Đường đi

 Tính chất đường đi ngắn nhất

 Đường đi ngắn nhất từ một đỉnh

Thuật toán Dijkstra

 Đường đi ngắn nhất giữa mọi đỉnh

Thuật toán Floyd–Warshall
1
Đường Đi – Định Nghĩa

 Trong đồ thị vô hướng 
 = , 

 Đường đi

 là dãy  các đỉnh , 	,  , 

2 đỉnh liên tiếp , 
 được nối bởi 1 cạnh trong .

 được gọi là đường đi từ  đến 

 Chu trình

 là đường đi , 	,  ,  với  > 1

 trong đó  đỉnh đầu tiên phân biệt và  = 

 Với đồ thị có hướng, trong một đường đi hay 
chu trình, 2 đỉnh liên tiếp ( , 
) phải là một
cung thuộc 
2
Đường Đi – Trọng Số
Đồ thị có hướng 
 = ,  với hàm trọng số
cung : 	 → . Trọng số của đường đi
   →  → ⋯ →  được định nghĩa:
   , 

Ví dụ:    2
3
Đường Đi Ngắn Nhất – Định Nghĩa
Đường đi ngắn nhất (ĐĐNN) từ  đến  là
đường đi có trọng số nhỏ nhất từ  đến . 
Trọng số đường đi ngắn nhất từ  đến 
được định nghĩa:
 ,  = min   : 	đường	đi	từ		đến	
Chú ý: ,  = ∞	không tồn tại đường đi
từ  đến .
4
Đường Đi Ngắn Nhất – Tính Chất
Cấu trúc con tối ưu

 Một đường đi con của một đường đi 
ngắn nhất là một đường đi ngắn nhất

   , 	,  ,  là ĐĐNN từ  đến 

 , =  , 	,  , , là đường đi con của 
từ  đến , với 0 ≤ / ≤ 0 ≤ 

 , =  , 	,  , , là ĐĐNN từ  đến ,
5
Đường Đi Ngắn Nhất – Tính Chất
Cấu trúc con tối ưu – chứng minh

 Chia  thành các đoạn con 
123 
134 ,
145 

 Khi đó,      + , + ,

 Giả sử có đường ′, từ  đến ,, với trọng số
 ′, <  ,

 Khi đó, 
123 
1934 ,
145  là đường đi từ 
đến  với trọng số nhỏ hơn  

 Mâu thuẫn với giả thiết  là ĐĐNN từ  đến 
6
Đường Đi Ngắn Nhất – Tính Chất
Bất đẳng thức tam giác

 Với mọi đỉnh , , : ∈ , ta có
 ,  . , : + :, 
7
Đường Đi Ngắn Nhất – Tính Chất
Trọng số âm

 Nếu đồ thị 
 có chu trình với trọng số âm, một
số đường đi ngắn nhất có thể không tồn tại
8
Đường Đi Ngắn Nhất Từ Một Đỉnh Nguồn

 Bài toán. Từ một đỉnh nguồn < ∈ , tìm
đường đi ngắn nhất (trọng số <,  ) tới
mọi đỉnh  ∈ 

 Nếu tất cả các trọng số  ,  không âm, 
thì mọi đường đi ngắn nhất tồn tại

 Áp dụng chiến lược tham ăn có thể tìm
được lời giải tối ưu

 Do ĐĐNN có tính chất cấu trúc con tối ưu
9
Đường Đi Ngắn Nhất Từ Một Đỉnh Nguồn

 Chiến lược tham ăn:
1. Duy trì một tập = là các đỉnh sao cho độ
dài đường đi ngắn nhất từ < là xác định
2. Mỗi bước, thêm vào tập = đỉnh  ∈  − =
sao cho đường đi từ < đến  là nhỏ nhất
3. Cập nhật khoảng cách từ < đến các đỉnh
liền kề 
10
Thuật Toán Dijkstra

 Gọi đường đi từ < tới đỉnh  là đường đi đặc biệt
nếu đường đi đó chỉ đi qua các đỉnh trong =

 Dùng mảng >: Độ dài đường đi từ < tới  lưu
trong >[]

 Ban đầu =     <,  với < ≠ 
11
< =    = 
Thuật Toán Dijkstra

 Dùng mảng >: Độ dài đường đi từ < tới  lưu
trong >[]

 Ban đầu =     <,  với 
< ≠ 

 Tại mỗi bước:

 Chọn một đỉnh  không thuộc = sao cho >  nhỏ
nhất, thêm  vào =. Khi đó >  là đường đi ngắn
nhất từ < đến 

 Sau đó xác định lại các >  với  ở ngoài =
>  = min >  , >[] 	+ 	(, )

 Lặp lại cho tới khi = gồm tất cả các đỉnh của đồ thị
12
Thuật Toán Dijkstra – Minh Họa
Ban đầu
=  {0}
> 0  0
> 1  ∞
> 2 = 9
> 3 = 2
> 4 = 5
13
0
3 2
1 4
2
5
9
1 4
8
1
Thuật Toán Dijkstra – Minh Họa
Thêm 3 vào =
= = {0, 3}
> 0 = 0
> 1 = min ∞, >[3] 	+ 1 = 3
> 2 = min 9, >[3] 	+ ∞ =9
> 3 = 2
> 4 = min 5, >[3] 	+ ∞ =5
14
0
3 2
1 4
2
5
9
1 4
8
1
Thuật Toán Dijkstra – Minh Họa
Thêm 1 vào =
= = {0, 3, 1}
> 0 = 0
> 1 = 3
> 2 = min 9, >[1] 	+ 4 =7
> 3 = 2
> 4 = min 5, >[1] 	+ ∞ =5
15
0
3 2
1 4
2
5
9
1 4
8
1
Thuật Toán Dijkstra – Minh Họa
Thêm 4 vào =
= = {0, 3, 1, 4}
> 0 = 0
> 1 = 3
> 2 = min 7, >[4] 	+ 1 =6
> 3 = 2
> 4 = 5
16
0
3 2
1 4
2
5
9
1 4
8
1
Thuật Toán Dijkstra – Minh Họa
Thêm 2 vào =
= = {0, 3, 1, 4,2}
> 0 = 0
> 1 = 3
> 2 = 6
> 3 = 2
> 4 = 5
>  lưu độ dài đường đi
ngắn nhất từ <  0 tới  với mọi  ∈ V
17
0
3 2
1 4
2
5
9
1 4
8
1
Thuật Toán Dijkstra – Bài Tập
=  {A, C, E, B, D}
> A  0 > B  7 > C  3 > D  9 > E  5
18
Thuật Toán Dijkstra – Mã Giả
>[<] 	← 0
for each  ∈ – {<} do
>[] 	← ∞
= ← ∅
S ← 
while S	 ≠ ∅ do
	 ← EXTRACT −MIN(S)
= ← = ∪ 
for each  ∈ [>0  do
if >[] 	> 	>[] 	+ 	(, ) then
>[] 	← >[] 	+ 	(, )
19
Đồ Thị Không Trọng Số
Giả sử (, ) = 1 cho mọi (, ) ∈ . Có áp dụng
được thuật toán Dijkstra không?

 Sử dụng hàng đợi FIFO thay vì hàng đợi ưu tiên
Tìm kiếm theo bề rộng (BFS)
while S	 ≠ ∅ do
	 ← DEQUEUE(S)
for each  ∈ [>0  do
if >  = ∞ then
>[] 	← >[] 	+ 1
ENQUEUE(S, )
Phân tích: Thời gian = ^( + 	)
20
Tìm Kiếm Theo Bề Rộng – Minh Họa
21
Đường Đi Ngắn Nhất Giữa Mọi Cặp Đỉnh
Từ một đỉnh nguồn

Thuật toán Dijkstra’s
Giữa mọi cặp đỉnh

Thuật toán Dijkstra’s  lần

Chiến lược tham ăn

Thuật toán Floyd-Warshall

Chiến lược quy hoạch động
22
Thuật Toán Floyd-Warshall
Định nghĩa _,   trọng số đường đi ngắn
nhất từ / tới 0 chỉ đi qua các đỉnh trong tập
đỉnh =  1,2,  , 
Khi đó, /, 0 = _, ` , ban đầu _,  = a,
23
Thuật Toán Floyd-Warshall

 Nếu đỉnh  nằm trên đường đi ngắn nhất từ / tới 0 thì
đường đi từ / tới  và đường đi từ  tới 0 là đường đi
ngắn nhất

 Nếu _,  là độ dài đường đi không qua , tức là
đường đi này chỉ đi qua các đỉnh trong =  , khi đó
_,
  _,


 Nếu _,  là độ dài đường đi qua , thì trên đường
đi này đoạn từ / tới  có độ dài _  , còn đoạn từ
 tới 0 có độ dài _, 

 Do đó
_,
  min
_,
 , _
 + _,

24
Thuật Toán Floyd-Warshall – Minh Họa
  0, tập =  rỗng, _,   a,
25
1 2 3 4
1 0 5 ∞ ∞
2 50 0 15 5
3 30 ∞ 0 15
4 15 ∞ 5 0
1 4
2 3
5 3050
15
5
15
15
5
Thuật Toán Floyd-Warshall – Minh Họa
_,
  min
_,
 , _
 + _,

26
1 2 3 4
1 0 5 ∞ ∞
2 50 0 15 5
3 30 ∞ 0 15
4 15 ∞ 5 0
1 2 3 4
1 0 5 ∞ ∞
2 50 0 15 5
3 30 35 0 15
4 15 20 5 0
_,

_,

1 4
2 3
5 3050
15
5
15
15
5
Thuật Toán Floyd-Warshall – Minh Họa
_,
  min
_,
 , _
 + _,

27
1 2 3 4
1 0 5 ∞ ∞
2 50 0 15 5
3 30 35 0 15
4 15 20 5 0
1 2 3 4
1 0 5 20 10
2 50 0 15 5
3 30 35 0 15
4 15 20 5 0
_,

_,
1 4
2 3
5 3050
15
5
15
15
5
Thuật Toán Floyd-Warshall – Minh Họa
_,
  min
_,
 , _
 + _,

28
1 2 3 4
1 0 5 20 10
2 50 0 15 5
3 30 35 0 15
4 15 20 5 0
1 2 3 4
1 0 5 20 10
2 45 0 15 5
3 30 35 0 15
4 15 20 5 0
_,
_,
b
1 4
2 3
5 3050
15
5
15
15
5
Thuật Toán Floyd-Warshall – Minh Họa
_,
  min
_,
 , _
 + _,

29
1 2 3 4
1 0 5 20 10
2 45 0 15 5
3 30 35 0 15
4 15 20 5 0
1 2 3 4
1 0 5 15 10
2 20 0 10 5
3 30 35 0 15
4 15 20 5 0
_,
b
_,
c
1 4
2 3
5 3050
15
5
15
15
5
Thuật Toán Floyd-Warshall – Mã Giả
for  ← 1 to d do
for  ← 1 to d do
for  ← 1 to d do
if _, > _ + _, then
_, ← _ + _,

 Thời gian chạy e db

 Đơn giản

 Hiệu quả
30