Bài giảng Lý thuyết đồ thị (Graph Theory) - Chương 5: Bài toán đường đi ngắn nhất. Thuật toán tìm bao đóng bắt cầu - Trần Quốc Việt

Nội dung text: Bài giảng Lý thuyết đồ thị (Graph Theory) - Chương 5: Bài toán đường đi ngắn nhất. Thuật toán tìm bao đóng bắt cầu - Trần Quốc Việt

1. 21/12/2013  Nguyễn Cam –Chu Đức Khánh, Lý thuyết đồ thị - NXB Trẻ Tp. HCM, 1998.  Kenneth H. Rosen: Discrete Mathematics and its Applications, 7 Edition, McGraw Hill, 2010. TRẦN QUỐC VIỆT 2  Đồ thị có trọng số: Là đơn đồ thị, trong đó mỗi cạnh được gán một giá  Nhiều bài toán có thể được mô hình hóa bằng đồ thị có trọng số: trị số, gọi là trọng số của cạnh Ví dụ:Mô hình hóa một hệ thống đường hàng không nối giữa các  Kí hiệu: w(e) là trọng số của cạnh e thành phố Ví dụ: 4 e8 5 A  Trọng số mỗi cạnh= Khoảng cách e3 1 1 8 e1 5 e6 6 6 2 e 3 2 7 4 e5 3 e 4 e 7 2 3 1
2. 21/12/2013 Ví dụ:Mô hình hóa một hệ thống đường hàng không nối giữa các Ví dụ:Mô hình hóa một hệ thống đường hàng không nối giữa các thành phố thành phố Trọng số mỗi cạnh= Giá vé Trọng số mỗi cạnh= Thời gian bay  Độ dài của một đường đi trong đồ thị có trọng số là tổng trọng số của tất cả các cạnh có trong đường đi đó. Ví dụ: Tìm một đường đi từ San Francisco đến Miami sao cho  Tìm đường đi ngắn nhất giữa 2 đỉnh trong đồ thị là một trong tổng tiền vé là ít nhất. nhiều vấn đề liên quan đến đồ thị có trọng số. Ví dụ 4 e8 5 A . Các đường đi từ 4 đến 6: e3 1 1 4e85e66. Độ dài: 5+6=12 8 e1 5 e6 4e85e77e56. Độ dài: 5+3+2=10 6 6 2 4e32e23e46. Độ dài: 1+4+3=8 3 2 e7 e 4 . Đường đi ngắn nhất giữa 4 và 6 là 5 3 e 4 e 7 2 4e32e23e46 với độ dài 8. 3 2
3. 21/12/2013  Cho đồ thị có trọng số G= , |V|=n  Nếu đường đi s . . . r . . . t là đường đi ngắn nhất từ s đến t thì  Ma trận trọng số của G được định nghĩa: s r và r t cũng là các đường đi ngắn nhất. w({vi,vj}) nếu (vi,vj) E W = (wij)nxn , Với wij=  (với =0,- hoặc + ) nếu {vi,vj} E Ví dụ min 4 e8 1 2 3 4 5 6 7 5 A 1 8 e3 1 1  . . . . . . t 2 8 4 1 s . . . . . . . .  r 8 e1 3 4 3 5 e6 4 1 5 6 6 2 5 5 6 3 min min 3 2 6 3 6 2 e7 4 7 3 2 e5 3 e 4 e 7 2 Ma trận trọng số 3  Chứng minh:  Gọi p: là đường đi có độ dài nhỏ nhất từ s đến t p1:là đoạn đường từ s đến r trên p p2:là đoạn đường từ r đến t trên p p 1 p2 s . . . . . . . .  r  . . . . . . t p Giả sử tồn tại đường đi p1’≠p1 từ s đến r nhỏ hơn p1. Khi đó: l(p)=l(p1’)+l(p2)<l(p1)+l(p2)=l(p) Vô lý, vì p là đường đi ngắn nhất từ s đến t p1 là ngắn nhất C/m tương tự: P2 cũng là đường đi ngắn nhất 3
4. 21/12/2013 Bài toán: Cho G=(V,E) đơn đồ thị vô hướng (hoặc có hướng),w(ei) 0 là trọng số của cạnh (cung) ei. Tìm đường đi có độ dài ngắn nhất từ đỉnh đỉnh s cho trước đến các đỉnh khác trong G? . Một số kí hiệu sử dụng: . Ma trận khoảng cách/ma trận trọng số được định nghĩa:  Gán nhãn cho đỉnh v (L(v), P(v)): Đường đi từ s đến v có độ dài là L(v), đỉnh trước kề với v trên đường đi là P(v). w(i,j) Nếu (i,j) E W=(wij)nxn, wij=  S=Tập các đỉnh đã xét, R = V-S + Nếu (i,j) E 4 e8 A 1 2 3 4 5 6 7 5 1 e3 1 8 1 8 e1 2 8 4 1 5 e6 6 6 2 3 4 3 3 e 2 4 1 5 7 e 4 5 3 e4 5 5 6 3 7 e2 6 3 6 2 3 7 3 2 Procedure Dijsktra(G: Có trọng số và liên thông,s: Đỉnh nguồn) Begin R:=V; For each v in R do Begin L[v]: = ∞; ( ,-) Khởi tạo D (0,-) P[v]: = - ; e8 5 A V A B C D E F G end e3 1 R A B C D E F G 8 e L[s]=0; ( ,-) 1 E e6 L 0 ( ,-) 6 F ( ,-) While (R≠) B P - - - - - - - 3 2 e7 Begin v = Đỉnh trong R có L[v] nhỏ nhất; 4 e5 3 e 4 e R=R-{v} G 2 ( ,-) For each i in (R  Tập đỉnh kề với v) do C Trong R, chọn v = A ( ,-) If (L[i]> L[v]+w[v][i]) then Các đỉnh có thể được cập nhật lại: B R=R-{A} L[i]:=L[v]+w[v][i]; P[i]=v; end End 4
5. 21/12/2013 ( ,-) (9,B) D (0,-) D (0,-) e8 e8 5 5 A V A B C D E F G A e3 e3 V A B C D E F G 1 R B C D E F G 1 8 e 8 e ( ,-) 1 ( ,-) 1 R C D E F G E e6 L 0 8 E e6 ( ,-) 6 F (8,A) ( ,-) 6 F (8,A) L 0 8 12 9 B P - A - - - - - B e 3 2 e 3 2 P - A B B - - - 7 4 7 4 e5 3 e e5 3 e 4 e 4 e G 2 G 2 ( ,-) ( ,-) C Trong R, chọn v = B C Trong R, chọn v = D ( ,-) (12,B) Các đỉnh có thể được cập nhật lại: Các đỉnh có thể được cập nhật lại: E Các đỉnh D và C R=R-{D} R=R-{B} (9,B) (9,B) D (0,-) D (0,-) e8 e8 5 5 A A e3 V A B C D E F G e3 1 1 V A B C D E F G 8 e 8 e ( ,-) 1 R C E F G (15,C) 1 E e6 E e6 R E F G 6 F 6 F (14,D) (8,A) B L 0 8 12 9 14 (14,D) (8,A) B L 0 8 12 9 14 15 e 3 2 P - A B B D - - e 3 2 7 4 7 4 P - A B B D C - e5 3 e e5 3 e 4 e 4 e G 2 G 2 ( ,-) ( ,-) C Trong R, chọn v = C C Trong R, chọn v =E (12,B) (12,B) Các đỉnh có thể được cập nhật lại: F Các đỉnh có thể được cập nhật lại: F,G R=R-{C} R=R-{E} 5
6. 21/12/2013 (9,B) (9,B) D (0,-) D (0,-) e8 e8 5 5 e3 A e3 A 1 V A B C D E F G 1 V A B C D E F G 8 e 8 e (15,C) 1 (15,C) 1 E e6 R F G E e6 R G 6 F 6 F (14,D) (8,A) B L 0 8 12 9 14 15 17 (14,D) (8,A) B L 0 8 12 9 14 15 17 e 3 2 e 3 2 7 4 P - A B B D C E 7 4 P - A B B D C E e5 3 e e5 3 e 4 e 4 e G 2 G 2 (17,E) (17,E) C Trong R, chọn v =F C Trong R, chọn v =G (12,B) (12,B) Các đỉnh có thể được cập nhật lại: G Các đỉnh có thể được cập nhật lại:  R=R-{F} R=R-{G}=. Kết thúc V A B C D E F G (9,B) R  Thuật toán Dijkstra dùng được cho cả đồ thị vô hướng và có D (0,-) e8 hướng 5 L 0 8 12 9 14 15 17 A e3 2 1 P - A B B D C E Độ phức tạp của thuật toán Dijkstra là O(n ) 8 e (15,C) 1 E  Thuật toán Dijkstra chỉ sử dụng với G không có cạnh có trọng số âm (14,D) F (8,A) B e 3 7 4 Đền Độ dài Đường đi 3 e 4 e G 2 đỉnh ĐĐNN Tìm đường đi ngắn nhất từ B (17,E) C 8 A-B đỉnh 3 đến đỉnh 5? (12,B) C 12 A-B-C D 9 A-B-D Cây bao trùm Dijkstra Kết quả Khi thực hiện thuật toán Dijkstra, ta thu được một cây E 14 A-B-D-E bao trùm của G gọi là cây bao trùm Dijkstra của G gốc s với F 15 A-B-CF khoảng cách ngắn nhất từ s đến từng đỉnh khác G 17 A-B-D-E-G 6
7. 21/12/2013 1) Cho đồ thị, chạy thuật toán Dijkstra, tìm đường đi ngắn nhất 2. Chạy thuật toán Dijkstra, tìm đường đi ngắn nhất đến các đỉnh, đến các đỉnh bắt đầu từ đỉnh v5  Bắt đầu từ đỉnh A  Bắt đầu từ đỉnh G A B C D E F V V V V V V 2 7 4 1 2 3 4 5 6 B C V V V A 2 1 1 2 3 V1 0 7 2 2 4 1 2 1 2 3 B 2 2 2 4 V 0 4 1 2 1 3 2 4 C 2 3 0 3 A D E H 2 V3 D 2 4 3 4 V 4 0 V4 V5 V 4 1 3 1 6 6 E 4 3 4 V 2 2 0 F 7 G 5 F 1 3 1 0 V6  Xét đơn đồ thị đồ thị có hướng có trọng số G= : ◦ Tập đỉnh: V={v1, v2, , vn} ◦ Ma trận khoảng cách: W = (wij) w(i,j) Nếu (i,j) E W=(wij)nxn, wij= + Nếu (i,j) E  Thuật toán Floyd giúp xác định tất cả các đường đi ngắn nhất giữa tất cả các cặp đỉnh. 7
8. 21/12/2013 Thuật toán Floyd xây dựng dãy các ma trận n n Wk (0 k n) như sau: Procedure Floyd(G: liên thông có ma trận trọng số W)  Định lý * Begin Thuật toán Floyd cho ta ma trận W = Wn là ma W0 := W trận khoảng cách nhỏ nhất của đồ thị G. For k=1 to n do For i=1 to n do For j =1 to n do Chứng minh: Bài tập if (Wk-1[i,j]>Wk-1[i,k]+Wk-1[k,j]) then Wk[i,j]=Wk-1[i,k]+Wk-1[k,j] else Wk[i,j]=Wk-1[i,j]; End Tính W1 (k=1) W W0[1,2] 7 4 V1 V2 V3 7 2 7 2 7 2 2 1 4 1 4 1 4 1 2 1 3 3 3 3 4 2 4 4 4 V V V 4 5 6 2 2 2 2 2 9 1 1 1 W [5,1] W0[5,2] 0 i=5 J=2 W0[5,2]>w0[5,1]+w0[1,2] Nên W1[5,2]= w0[5,1]+w0[1,2] 8
9. 21/12/2013 Tính W1 (k=1) W0[1,3] 7 2 7 2 7 2 4 1 4 1 4 1 3 3 3 4 4 4 W0[5,1] 2 2 2 9 2 1 1 2 9 2 4 W [5,3] W0[5,3]<w0[5,1]+w0[1,3] 0 k=1 i=5 J=3: 1 Nên W1[5,3]=W0[5,3] 7 11 2 8 7 11 2 8 14 4 1 4 1 7 3 3 4 8 5 4 8 5 11 2 9 2 4 10 2 9 2 4 10 5 1 5 2 1 5 2 8 9
10. 21/12/2013 6 10 2 7 13 9 6 9 2 7 12 4 1 7 3 9 3 5 1 6 3 3 4 8 5 11 7 4 7 9 5 10 2 8 2 4 9 5 2 8 2 4 9 5 1 5 2 8 4 1 4 6 2 7 9 6 9 2 7 12 •Độ dài đường đi ngắn . Đặt P0[i, j] = j nếu có cung vivj. nhất từ đỉnh 4 đến . P0[i, j] = : không xác định. 3 7 3 5 1 6 đỉnh 6 là . P [i, j]: đỉnh liền sau i trên đường đi ngắn nhất từ i W*[4,6] =10 k 7 4 7 9 5 3 đến j. •Độ dài đường đi ngắn 7 4 7 9 5 10 nhất từ đỉnh 5 đến . Đường đi ngắn nhất từ đỉnh i đến đỉnh j được xác định bởi dãy: 2 6 2 4 7 5 đỉnh 4 là W*[5,4] =4 . i, P*[i,j],P*[P*[i,j],j], P*[P*[P*[i,j],j],j],j], ,j 4 1 4 6 2 7 . 10
11. 21/12/2013 W0=W; For k=1 to n do 6 For i=1 to n do For j=1 to n do if (Wk-1[i,j] > Wk-1[i,k] + Wk-1[k,j]) then 1 begin 2 4 Wk[i,j] = Wk-1[i,k] + Wk-1[k,j]; Pk[i,j] = Pk-1[i,k]; 7 4 end else 1 begin 7 11 Wk[i,j] = Wk-1[i,j]; 5 Pk[i,j] = Pk-1[i,j]; end 3 7 5 2 3 7 5 2 3 7 6 3 4 7 6 3 4 W = P0 = W = P1 = 0 1 4 1 11 4 1 9 1 2 3 1 2 1 11
12. 21/12/2013 7 5 13 2 3 2 7 5 13 2 3 2 7 6 3 4 7 6 3 4 W = P2 = W = P3 = 2 3 4 1 8 7 4 1 8 7 1 2 2 2 1 2 2 2  Thuật toán Floyd có thể áp dụng cho đồ thị G vô hướng W* = W = 4 P* = P4 = (thay mỗi cạnh (u,v) bởi cặp cung có hướng (u,v) và (v,u)). 17 7 5 13 2 2 3 2  Đồ thị G có hướng là liên thông mạnh u,v V, u≠v W*[u,v]< . 10 7 7 6 4 4 3 4  Đồ thị G có hướng có chu trình  u V, W*[u,u]<  Độ phức tạp của thuật toán Floyd: O(|V|3) 4 1 8 7 1 2 2 2 12
13. 21/12/2013 Input: W là ma trận trọng số của đơn đồ thị G Cho đơn đồ thị có trọng số G, không có chu trình s: Đỉnh nguồn âm, với ma trận trọng số W Output: L: L[v]Khoảng cách ngắn nhất từ s đến các đỉnh v Thuật toán Bellman-Ford cho phép tìm đường đi P: P[v] là đỉnh trước đỉnh v ngắn nhất từ một đỉnh s đến tất cả các đỉnh còn lại Ma trận trọng số w(i,j) Nếu (i,j) E W=(wij)nxn, wij= + Nếu (i,j) E // Khởi tạo stop=false;k=0; while (not stop) do //Mỗi đỉnh i, gán nhãn bởi cặp (pre[i], l[i]) begin stop=true;k=k+1; For i=1 to n do For each (i,j) in E do begin if L[j]>L[i]+w[i][j] then P[i]=-; begin L[j]=L[i]+w[i][j]; P[j]=i; stop=false; if (i=s) then end L[i]=0 if (k>n) then else begin if (stop=false) print “đồ thị có chu trình âm” L[i]= ; stop=true; end end end 13
14. 21/12/2013  Thuật toán Bellman-Ford tìm đường đi ngắn nhất Ví dụ: s=6 2 3 từ một đỉnh (đỉnh nguồn) đến tất cả các đỉnh còn lại 1 1 5 2 (giống như Dijkstra) 4 3 1 3 6  Thuật toán Bellman-Ford dùng được cho cả đồ thị 2 5 2 vô hướng và có hướng, cho phép có cạnh âm, miễn 4 là không có chu trình âm Đỉnh 1 2 3 4 5 6 3 Khởi tạo (-, ) (-, ) (-, ) (-, ) (-, ) (-,0)  Độ phức tạp của thuật toán là O(n ) Lặp lần 1 (-, ) (-, ) (6,1) (-, ) (6,2) (-,0) Lặp lần 2 (3,3) (5,6) (6,1) (3,3) (6,2) (-,0) Lặp lần 3 (3,3) (4,4) (6,1) (3,3) (6,2) (-,0) Lặp lần 4 (3,3) (4,4) (6,1) (3,3) (6,2) (-,0) . . . ij (k)  Cho đơn đồ thị G có tập đỉnh V={v1,v2, ,vn}, đỉnh  Định lý: Gọi A =(a ) là ma trận kề của đơn đồ thị G, a ij = 1 vj gọi là khả liên (reachable) từ đỉnh vi nếu có một có một đường đi độ dài k từ đỉnh vi đến đỉnh vj đường đi từ vi đến vj  C/m: Sử dụng quy nạp  Ma trận kề A=(a ) của G là một ma trận Boole (1) ij ◦ Với k=1, a ij=1 có đường đi trực tiếp (độ dài 1) từ vi đến vj  Kí hi u: A(k) = A(k-1) A v i phép c ng/nhân các (k) ệ ớ ộ ◦ Giả sử a ij =1 có đường đi độ dài k từ vi đến vj phần tử tương ứng với phép toán or/and trên bit: ◦ Ta có n (k 1) (k ) aij ait atj t 1 14
15. 21/12/2013 n (k) (k 1) (k ) Ma trận khả liên R =(rij): aij ait atj t 1 (k ) (1) (2) (k ) (k+1) (k) R A A A a ij =1 t,a it=1  atj =1 (k) ◦ a it =1 có đường đi độ dài k từ vi đến vt Nhận xét: rij =1 có một đường đi từ đỉnh vi đến đỉnh ◦ atj =1 có đường đi độ dài 1 từ vt đến đến vj vj Vậy có đường đi có độ dài k+1 từ vi đến vj vi vj Đường đi từ vt đến Đường đi từ vi đến v t Vj có độ dài 1 (cạnh/cung trực tiếp) Vt có độ dài k 1. Cài đặt thuật toán Dijkstra  Input: A: Ma trận kề của đơn đồ thị G a) Tìm đường đi ngắn nhất đến tất cả các đỉnh khác trong đồ  Output: R: ma trận khả liên của G thị từ một đỉnh cho trước. In ra tất cả các đường đi cùng với khoảng cách tìm được) R=A b) Tìm đường đi ngắn nhất từ đỉnh s đến đỉnh t cho trước For k=1 to n do 2. Cài đặt thuật toán Floyd For i=1 to n do a) Tìm ma trận k/c ngắn nhất For j=1 to n do b) In ra đường đi cùng với k/c ngắn nhất tìm được giữa 2 R[i][j]=R[i][j] or (R[i][k] and R[k][j]); đỉnh s, t cho trước Return R 15
16. 21/12/2013 3. Cài đặt thuật toán : a) Kiểm tra tính liên thông mạnh của đồ thị có hướng b) Kiểm tra một đồ thị có chu trình hay không c) Kiểm tra 2 đỉnh u, v có khả liên hay không (có đường đi từ u đến v hay không) 4. Cài đặt thuật toán WARSHALL 5. Cài đặt thuật toán 16