Giáo trình Thiết kế & Đánh giá thuật toán - Bài giảng 13: Đườ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