›
›

Bài giảng Lý thuyết đồ thị - Chương 5: Bài toán đường đi ngắn nhất

pdf 78 trang ngocly 3020
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Lý thuyết đồ thị - Chương 5: Bài toán đường đi ngắn nhất", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pdfbai_giang_ly_thuyet_do_thi_chuong_5_bai_toan_duong_di_ngan_n.pdf

Nội dung text: Bài giảng Lý thuyết đồ thị - Chương 5: Bài toán đường đi ngắn nhất

  1. Chương 5 BÀI TOÁN ĐƯỜNG ĐI NGẮN NHẤT Nguyễn Đức Nghĩa Toán rời rạc, Fall 2005 Bài toán đường đi ngắn nhất 1
  2. Nội dung 5.1. Bài toán đường đi ngắn nhất (ĐĐNN) 5.2. Tính chất của ĐĐNN, Giảm cận trên 5.3. Thuật toán Bellman-Ford 5.4. Thuật toán Dijkstra 5.5. Đường đi ngắn nhất trong đồ thị không có chu trình 5.6. Thuật toán Floyd-Warshal Nguyễn Đức Nghĩa Toán rời rạc, Fall 2005 Bài toán đường đi ngắn nhất 2
  3. 5.1. Bài toán đường đi ngắn nhất Cho đơn đồ thị có hướng G = (V,E) với hàm trọng số w: E R (w(e) được gọi là độ dài hay trọng số của cạnh e) Độ dài của đường đi P = v1 v2 vk là số k 1 w()(,) P  w vi v i 1 i 1 Đường đi ngắn nhất từ đỉnh u đến đỉnh v là đường đi có độ dài ngắn nhất trong số các đường đi nối u với v. Độ dài của đường đi ngắn nhất từ u đến v còn được gọi là khoảng cách từ u tới v và ký hiệu là (u,v). Nguyễn Đức Nghĩa Toán rời rạc, Fall 2005 Bài toán đường đi ngắn nhất 3
  4. Ví dụ Cho đồ thị có trọng số G = (V, E), và đỉnh nguồn s V, hãy tìm đường đi ngắn nhất từ s đến mỗi đỉnh còn lại. 3 a d 3 4 6 đỉnh nguồn 5 s 1 c 1 2 f 2 5 e 3 b 2 s a b c d e f weight 0 3 4 6 6 6 9 path s s,a s,a,b s,a,b,c s,a,d s,a,b,e s,a,b,e,f Nguyễn Đức Nghĩa Toán rời rạc, Fall 2005 Bài toán đường đi ngắn nhất 4
  5. Các ứng dụng thực tế Giao thông (Transportation) Truyền tin trên mạng (Network routing) (cần hướng các gói tin đến đích trên mạng theo đường nào?) Truyền thông (Telecommunications) Speech interpretation (best interpretation of a spoken sentence) Điều khiển robot (Robot path planning) Medical imaging Giải các bài toán phức tạp hơn trên mạng  Nguyễn Đức Nghĩa Toán rời rạc, Fall 2005 Bài toán đường đi ngắn nhất 5
  6. Các dạng bài toán ĐĐNN 1. Bài toán một nguồn một đích: Cho hai đỉnh s và t, cần tìm đường đi ngắn nhất từ s đến t. 2. Bài toán một nguồn nhiều đích: Cho s là đỉnh nguồn, cần tìm đường đi ngắn nhất từ s đến tất cả các đỉnh còn lại. 3. Bài toán mọi cặp: Tìm đường đi ngắn nhất giữa mọi cặp đỉnh của đồ thị.  Đường đi ngắn nhất theo số cạnh - BFS. Nguyễn Đức Nghĩa Toán rời rạc, Fall 2005 Bài toán đường đi ngắn nhất 6
  7. Nhận xét Các bài toán được xếp theo thứ tự từ đơn giản đến phức tạp Hễ có thuật toán hiệu quả để giải một trong ba bài toán thì thuật toán đó cũng có thể sử dụng để giải hai bài toán còn lại Nguyễn Đức Nghĩa Toán rời rạc, Fall 2005 Bài toán đường đi ngắn nhất 7
  8. Giả thiết cơ bản Nếu đồ thị có chu trình âm thì độ dài đường đi giữa hai đỉnh nào đó có thể làm nhỏ tuỳ ý: -18 b c Xét đường đi từ a đến e: a 3 5 P: a (d b c d) e 2 5 w(P) = 7-10 -∞, khi  + ∞ d e Giả thiết: Đồ thị không chứa chu trình độ dài âm (gọi tắt là chu trình âm) Nguyễn Đức Nghĩa Toán rời rạc, Fall 2005 Bài toán đường đi ngắn nhất 8
  9. Trọng số âm Độ dài của đường đi ngắn nhất có thể là hoặc – . a -4 b 3 -1 h i 3 4 2 đỉnh s c 6 d g nguồn 5 11 8 0 5 -3 - -8 3 2 e 3 f - - 7 j -6 chu trình âm không đạt tới được từ s Nguyễn Đức Nghĩa Toán rời rạc, Fall 2005 Bài toán đường đi ngắn nhất 9
  10. 5.1. Bài toán đường đi ngắn nhất (ĐĐNN) 5.2. Tính chất của ĐĐNN, Giảm cận trên 5.3. Thuật toán Bellman-Ford 5.4. Thuật toán Dijkstra 5.5. Đường đi ngắn nhất trong đồ thị không có chu trình 5.6. Thuật toán Floyd-Warshal Nguyễn Đức Nghĩa Toán rời rạc, Fall 2005 Bài toán đường đi ngắn nhất 10
  11. Các tính chất của ĐĐNN Tính chất 1. Đường đi ngắn nhất luôn có thể tìm trong số các đường đi đơn. • CM: Bởi vì việc loại bỏ chu trình độ dài không âm khỏi đường đi không làm tăng độ dài của nó. u v C w(C) 0 Tính chất 2. Mọi đường đi ngắn nhất trong đồ thị G đều đi qua không quá n-1 cạnh, trong đó n là số đỉnh. • Như là hệ quả của tính chất 1 Nguyễn Đức Nghĩa Toán rời rạc, Fall 2005 Bài toán đường đi ngắn nhất 11
  12. Các tính chất của ĐĐNN Tính chất 3: Giả sử P = ‹v1, v2, , vk› là đđnn từ v1 đến vk. Khi đó, Pij = ‹vi, vi+1, , vj› là đđnn từ vi đến vj, với 1 i j k. (Bằng lời: Mọi đoạn đường con của đường đi ngắn nhất đều là đường đi ngắn nhất) CM. Phản chứng. Nếu Pij không là đđnn từ vi đến vj, thì tìm được P’ij là đường đi từ vi đến vj thoả mãn w(P’ij) < w(Pij). Khi đó gọi P’ là đường đi thu được từ P bởi việc thay đoạn Pij bởi P’ij, ta có w(P’) < w(P) ?! v i v P j ij vk v1 P’ij Nguyễn Đức Nghĩa Toán rời rạc, Fall 2005 Bài toán đường đi ngắn nhất 12
  13. Các tính chất của ĐĐNN Ký hiệu: δ(u, v) = độ dài đđnn từ u đến v (gọi là khoảng cách từ u đến v) Hệ quả: Giả sử P là đđnn từ s tới v, trong đó P = s p' u v. Khi đó δ(s, v) = δ(s, u) + w(u, v). Tính chất 4: Giả sử s V. Đối với mỗi cạnh (u,v) E, ta có δ(s, v) δ(s, u) + w(u,v). Nguyễn Đức Nghĩa Toán rời rạc, Fall 2005 Bài toán đường đi ngắn nhất 13
  14. Đường đi ngắn nhất xuất phát từ một đỉnh Single-Source Shortest Paths Nguyễn Đức Nghĩa Toán rời rạc, Fall 2005 Bài toán đường đi ngắn nhất 14
  15. Biểu diễn đường đi ngắn nhất Các thuật toán tìm đường đi ngắn nhất làm việc với hai mảng: d(v) = độ dài đường đi từ s đến v ngắn nhất hiện biết (cận trên cho độ dài đường đi ngắn nhất thực sự). p(v) = đỉnh đi trước v trong đường đi nói trên (sẽ sử dụng để truy ngược đường đi từ s đến v) . Khởi tạo (Initialization) for v V(G) do d[v]  p[v]  NIL d[s]  0 Nguyễn Đức Nghĩa Toán rời rạc, Fall 2005 Bài toán đường đi ngắn nhất 15
  16. Giảm cận trên (Relaxation) Sử dụng cạnh (u, v) để kiểm tra xem đường đi đến v đã tìm được có thể làm ngắn hơn nhờ đi qua u hay không. u Relax(u, v) s v if d[v] > d[u] + w(u, v) z p(v) then d[v]  d[u] + w(u, v) p[v]  u d[v] > d[u] + w(u, v) Các thuật toán tìm đđnn khác nhau ở số lần dùng các cạnh và trình tự duyệt u p(v) chúng để thực hiện giảm cận . s v z Nguyễn Đức Nghĩa Toán rời rạc, Fall 2005 Bài toán đường đi ngắn nhất 16
  17. Nhận xét chung  ViÖc cµi ®Æt c¸c thuËt to¸n ®îc thÓ hiÖn nhê thñ tôc g¸n nh·n: • Mçi ®Ønh v sÏ cã nh·n gåm 2 thµnh phÇn (d[v], p[v]). Nh·n sÏ biÕn ®æi trong qu¸ tr×nh thùc hiÖn thuËt to¸n NhËn thÊy r»ng ®Ó tÝnh kho¶ng c¸ch tõ s ®Õn t, ë ®©y, ta ph¶i tÝnh kho¶ng c¸ch tõ s ®Õn tÊt c¶ c¸c ®Ønh cßn l¹i cña ®å thÞ. HiÖn nay vÉn cha biÕt thuËt to¸n nµo cho phÐp t×m ®®nn nhÊt gi÷a hai ®Ønh lµm viÖc thùc sù hiÖu qu¶ h¬n nh÷ng thuËt to¸n t×m ®®nn tõ mét ®Ønh ®Õn tÊt c¶ c¸c ®Ønh cßn l¹i. Nguyễn Đức Nghĩa Toán rời rạc, Fall 2005 Bài toán đường đi ngắn nhất 17
  18. Nội dung 5.1. Bài toán đường đi ngắn nhất (ĐĐNN) 5.2. Tính chất của ĐĐNN, Giảm cận trên 5.3. Thuật toán Bellman-Ford 5.4. Thuật toán Dijkstra 5.5. Đường đi ngắn nhất trong đồ thị không có chu trình 5.6. Thuật toán Floyd-Warshal Nguyễn Đức Nghĩa Toán rời rạc, Fall 2005 Bài toán đường đi ngắn nhất 18
  19. Thuật toán Ford-Bellman Richard Bellman 1920-1984 Lester R. Ford, Jr. 1927~ Nguyễn Đức Nghĩa Toán rời rạc, Fall 2005 Bài toán đường đi ngắn nhất 19
  20. Thuật toán Ford-Bellman ThuËt to¸n Ford - Bellman t×m ®êng ®i ng¾n nhÊt tõ ®Ønh s ®Õn tÊt c¶ c¸c ®Ønh cßn l¹i cña ®å thÞ. ThuËt to¸n lµm viÖc trong trêng hîp träng sè cña c¸c cung lµ tuú ý. Gi¶ thiÕt r»ng trong ®å thÞ kh«ng cã chu tr×nh ©m. §Çu vµo: §å thÞ G=(V,E) víi n ®Ønh x¸c ®Þnh bëi ma trËn träng sè w[u,v], u,v V, ®Ønh nguån s V; §Çu ra: Víi mçi v V Nguyễn Đức• Nghĩad[v] = (s, v); Toán rời rạc, Fall 2005 Bài toán đường đi ngắn nhất 20 • p[v] - ®Ønh ®i tríc v trong ®®nn tõ s ®Õn v.
  21. Mô tả thuật toán procedure Ford_Bellman; begin for v V do begin (* Khëi t¹o *) d[v] := w[s,v] ; p[v]:=s; end; d[s]:=0; p[s]:=s; for k := 1 to n-2 do (* n = |V| *) for v V \ {s} do for u V do if d[v] > d[u] + w[u,v] then begin d[v] := d[u] + w[u,v] ; p[v] := u ; end; end; Nguyễn Đức Nghĩa Toán rời rạc, Fall 2005 Bài toán đường đi ngắn nhất 21
  22. Nhận xét TÝnh ®óng ®¾n cña thuËt to¸n cã thÓ chøng minh trªn c¬ së nguyªn lý tèi u cña quy ho¹ch ®éng. §é phøc t¹p tÝnh to¸n cña thuËt to¸n lµ O(n3). Cã thÓ chÊm døt vßng lÆp theo k khi ph¸t hiÖn trong qu¸ tr×nh thùc hiÖn hai vßng lÆp trong kh«ng cã biÕn d[v] nµo bÞ ®æi gi¸ trÞ. ViÖc nµy cã thÓ x¶y ra ®èi víi k < n-2, vµ ®iÒu ®ã lµm t¨ng hiÖu qu¶ cña Nguyễn ĐứcthuËt Nghĩa to¸n trong ToánviÖc rời rạc, Fallgi¶i 2005 c¸c bµiBài toánto¸n đường đi ngắnthùc nhất 22
  23. Ví dụ x t 5 -2 6 8 -3 0 2 s 7 -4 7 9 y z Source: s Trình tự duyệt cạnh để giảm cận: (t, x), (t, y), (t, z), (x, t), (y, x), (y, z), (z, x), (z, s), (s, t), (s, y) Nguyễn Đức Nghĩa Toán rời rạc, Fall 2005 Bài toán đường đi ngắn nhất 23
  24. Lần 1 d[t] = 6 x p[t] = s t 5 6 -2 6 8 -3 0 2 s 7 -4 7 7 9 d[y] = 7 y z p[y] = s Nguyễn Đức Nghĩa Toán rời rạc, Fall 2005 Bài toán đường đi ngắn nhất 24
  25. Lần 2 x d[x] = 11 t 5 p[x] = t 11 6 -2 6 8 -3 0 2 s 7 -4 7 2 7 d[z] = 2 9 y z p[z] = t Relax (t, x), (t, y), (t, z), (x, t). Nguyễn Đức Nghĩa Toán rời rạc, Fall 2005 Bài toán đường đi ngắn nhất 25
  26. Lần 2 (tiếp) x d[x] = 4 t 5 p[x] = y 4 6 -2 6 8 -3 0 2 s 7 -4 7 7 2 9 y z Relax (y, x), (y, z), (z, x), (z, s), (z, s), (s, t), (s, y). Nguyễn Đức Nghĩa Toán rời rạc, Fall 2005 Bài toán đường đi ngắn nhất 26
  27. Lần 3 d[t] = 2 x p[t] = x t 5 4 2 -2 6 8 -3 0 2 s 7 -4 7 7 2 9 y z Nguyễn Đức Nghĩa Toán rời rạc, Fall 2005 Bài toán đường đi ngắn nhất 27
  28. Lần 4 x t 5 4 2 -2 6 8 -3 0 2 s 7 -4 7 -2 7 d[z] = -2 9 y z p[z] = t (không đổi) Nguyễn Đức Nghĩa Toán rời rạc, Fall 2005 Bài toán đường đi ngắn nhất 28
  29. Nhận xét §èi víi ®å thÞ tha tèt h¬n lµ sö dông danh s¸ch kÒ Ke-(v), v V, ®Ó biÓu diÔn ®å thÞ, khi ®ã vßng lÆp theo u cÇn viÕt l¹i díi d¹ng for u Ke (v) do if d[v] > d[u] + w[u,v] then begin d[v] := d[u] + w[u,v] ; p[v] := u ; end; ThuËt to¸n cã ®é phøc t¹p O(n.m). Nguyễn Đức Nghĩa Toán rời rạc, Fall 2005 Bài toán đường đi ngắn nhất 29
  30. Nội dung 5.1. Bài toán đường đi ngắn nhất (ĐĐNN) 5.2. Tính chất của ĐĐNN, Giảm cận trên 5.3. Thuật toán Bellman-Ford 5.4. Thuật toán Dijkstra 5.5. Đường đi ngắn nhất trong đồ thị không có chu trình 5.6. Thuật toán Floyd-Warshal Nguyễn Đức Nghĩa Toán rời rạc, Fall 2005 Bài toán đường đi ngắn nhất 30
  31. Thuật toán Dijkstra  Trong trêng hîp träng sè trªn c¸c cung lµ kh«ng ©m, thuËt to¸n do Dijkstra ®Ò nghÞ h÷u hiÖu h¬n rÊt nhiÒu so víi thuËt to¸n Ford-Bellman.  ThuËt to¸n ®îc x©y dùng dùa trªn thủ tục Edsger W.Dijkstra gán nhãn. Thoạt tiên nh·n của các đỉnh là t¹m (1930-2002) thêi. ë mçi mét bíc lÆp cã mét nh·n t¹m thêi trë thµnh nh·n cè ®Þnh. NÕu nh·n cña mét ®Ønh u trë thµnh cè ®Þnh th× d[u] sÏ cho ta ®é dµi cña ®®nn tõ ®Ønh s ®Õn u. Thuật toán kết thúc khi nhãn của tất cả các đỉnh trở thành cố định. Nguyễn Đức Nghĩa Toán rời rạc, Fall 2005 Bài toán đường đi ngắn nhất 31
  32. Thuật toán Dijkstra  §Çu vµo: §å thÞ cã híng G=(V,E) víi n ®Ønh, s V lµ ®Ønh xuÊt ph¸t, w[u,v], u,v V - ma trËn träng sè;  Gi¶ thiÕt: w[u,v] 0, u, v V.  §Çu ra: Víi mçi v V • d[v] = (s, v); • p[v] - ®Ønh ®i tríc v trong ®®nn tõ s ®Õn v. Nguyễn Đức Nghĩa Toán rời rạc, Fall 2005 Bài toán đường đi ngắn nhất 32
  33. Thuật toán Dijkstra procedure Dijkstra; Tập S: Chỉ cần cho chứng minh định lý begin for v V do begin (* Khëi t¹o *) d[v] := w[s,v] ; p[v]:=s; end; d[s] := 0; S := {s}; (* S – tËp ®Ønh cã nh·n cè ®Þnh *) T := V \ {s}; (* T lµ tËp c¸c ®Ønh cã nh·n t¹m thêi *) while T  do (* Bíc lÆp *) begin T×m ®Ønh u T tho¶ m·n d[u] = min{ d[z] : z T}; T := T \ {u}; S:= S  {u}; (* Cè ®Þnh nh·n cña ®Ønh u *) for v T do (* G¸n nh·n l¹i cho c¸c ®Ønh trong T *) if d[v] > d[u] + w[u,v] then begin d[v] := d[u] + w[u,v] ; p[v] := u ; end; Nguyễn Đứcend; Nghĩa Toán rời rạc, Fall 2005 Bài toán đường đi ngắn nhất 33 end;
  34. Thuật toán Dijkstra  Chó ý: NÕu chØ cÇn t×m ®êng ®i ng¾n nhÊt tõ s ®ªn t th× cã thÓ chÊm døt thuËt to¸n khi ®Ønh t trë thµnh cã nh·n cè ®Þnh. §Þnh lý 1. ThuËt to¸n Dijkstra t×m ®îc ®- êng ®i ng¾n nhÊt tõ ®Ønh s ®Õn tÊt c¶ c¸c ®Ønh cßn l¹i trªn ®å thÞ sau thêi gian O(n2).  CM: Rõ ràng thời gian tính là O(n2) Nguyễn Đức Nghĩa Toán rời rạc, Fall 2005 Bài toán đường đi ngắn nhất 34
  35. Chứng minh tính đúng đắn của Thuật toán Dijkstra y Ta sẽ CM với mỗi v S, d(v) = (s, v). P* • Qui nạp theo |S|. x • Cơ sở qui nạp: Với |S| = 1, rõ ràng là đúng. s • Chuyển qui nạp: v S  giả sử thuật toán Dijkstra bổ sung v vào S  d(v) là độ dài của một đường đi từ s đến v  nếu d(v) không là độ dài đđnn từ s đến v, thì gọi P* là đđnn từ s đến v  P* phải sử dụng cạnh ra khỏi S, chẳng hạn (x, y)  khi đó d(v)> (s, v) giả thiết = (s, x) + w(x, y) + (y, v) tính chất 3 (s, x) + w(x, y) (y, v) là không âm = d(x) + w(x, y) giả thiết quy nạp Nguyễn Đức Nghĩa d(y) Toán rời rạc, Fall 2005 Bài toán đường đi ngắn nhất 35 theo thuật toán
  36. Ví dụ 7 5 1 2 3 6 Tìm đường đi ngắn 2 1 2 10 nhất từ đỉnh 1 đến tất 1 3 cả các đỉnh còn lại 1 4 5 2 4 Đỉnh 1 Đỉnh 2 Đỉnh 3 Đỉnh 4 Đỉnh 5 Đỉnh 6 Khởi [0, 1] [1, 1]* [ , 1] [ , 1] [ , 1] [ , 1] tạo 1 - - [6, 2] [3, 2]* [ , 1] [8, 2] 2 - - [4, 4]* - [7, 4] [8, 2] 3 - - - - [6, 3] [5, 3]* 4 - - - - [6, 3]* - 5 - - - - - - Nguyễn Đức Nghĩa Toán rời rạc, Fall 2005 Bài toán đường đi ngắn nhất 36
  37. Cây đường đi ngắn nhất Tập cạnh {(p(v), v): v V \ {s} } tạo thành cây có gốc tại đỉnh nguồn s được gọi là cây đđnn xuất phát từ đỉnh s. 7 • Các cạnh màu đỏ 4 5 1 tạo thành cây đđnn 1 2 3 6 5 xuất phát từ đỉnh 1 2 1 2 • Số màu đỏ viết bên 1 10 cạnh mỗi đỉnh là độ 3 1 4 5 6 dài đường đi ngắn 2 4 nhất từ 1 đến nó. 3 Nguyễn Đức Nghĩa Toán rời rạc, Fall 2005 Bài toán đường đi ngắn nhất 37
  38. Nội dung 5.1. Bài toán đường đi ngắn nhất (ĐĐNN) 5.2. Tính chất của ĐĐNN, Giảm cận trên 5.3. Thuật toán Bellman-Ford 5.4. Thuật toán Dijkstra 5.5. Đường đi ngắn nhất trong đồ thị không có chu trình 5.6. Thuật toán Floyd-Warshal Nguyễn Đức Nghĩa Toán rời rạc, Fall 2005 Bài toán đường đi ngắn nhất 38
  39. Đường đi trong đồ thị không có chu trình Shortest Paths In Directed Acyclic Graphs Nguyễn Đức Nghĩa Toán rời rạc, Fall 2005 Bài toán đường đi ngắn nhất 39
  40. Đường đi trong đồ thị không có chu trình Mét trêng hîp riªng cña bµi to¸n ®êng ®i ng¾n nhÊt gi¶i ®îc nhê thuËt to¸n víi ®é phøc t¹p tÝnh to¸n O(n2), ®ã lµ bµi to¸n trªn ®å thÞ kh«ng cã chu tr×nh (cßn träng sè trªn c¸c cung cã thÓ lµ c¸c sè thùc tuú ý). KÕt qu¶ sau ®©y lµ c¬ së ®Ó x©y dùng thuËt to¸n nãi trªn: §Þnh lý 2. Gi¶ sö G lµ ®å thÞ kh«ng cã chu tr×nh. Khi ®ã c¸c ®Ønh cña nã cã thÓ ®¸nh sè sao cho mçi cung cña ®å thÞ chØ híng tõ ®Ønh cã chØ sè nhá h¬n ®Õn ®Ønh cã chØ sè lín h¬n, nghÜa lµ mçi cung cña nã cã thÓ biÓu diÔn díi d¹ng (v[i], v[j]), trong ®ã i < j . Nguyễn Đức Nghĩa Toán rời rạc, Fall 2005 Bài toán đường đi ngắn nhất 40
  41. Thuật toán đánh số đỉnh  Tríc hÕt nhËn thÊy r»ng: Trong ®å thÞ kh«ng cã chu tr×nh bao giê còng t×m ®îc ®Ønh cã b¸n bËc vµo b»ng 0. Thùc vËy, b¾t ®Çu tõ ®Ønh v1 nÕu cã cung ®i vµo nã tõ v2 th× ta l¹i chuyÓn sang xÐt ®Ønh v2. NÕu cã cung tõ v3 ®i vµo v2, th× ta l¹i chuyÓn sang xÐt v3, Do ®å thÞ lµ kh«ng cã chu tr×nh nªn sau mét sè h÷u h¹n lÇn chuyÓn nh vËy ta ph¶i ®i ®Õn ®Ønh kh«ng cã cung ®i vµo.  ThuËt to¸n ®îc x©y dùng dùa trªn ý tëng rÊt ®¬n gi¶n sau: Tho¹t tiªn, t×m c¸c ®Ønh cã b¸n bËc vµo b»ng 0. Râ rµng ta cã thÓ ®¸nh sè chóng theo mét thø tù tuú ý b¾t ®Çu tõ 1. TiÕp theo, lo¹i bá khái ®å thÞ nh÷ng ®Ønh ®· ®îc ®¸nh sè cïng c¸c cung ®i ra khái chóng, ta thu ®îc ®å thÞ míi còng kh«ng cã chu tr×nh, vµ thñ tôc ®îc lÆp l¹i víi ®å thÞ míi nµy. Qu¸ tr×nh ®ã sÏ ®îc tiÕp tôc cho ®Õn khi tÊt c¶ c¸c ®Ønh cña ®å thÞ ®îc ®¸nh sè. Nguyễn Đức Nghĩa Toán rời rạc, Fall 2005 Bài toán đường đi ngắn nhất 41
  42. Thuật toán đánh số đỉnh  §Çu vµo: §å thÞ cã híng G=(V,E) víi n ®Ønh kh«ng chøa chu tr×nh ®îc cho bëi danh s¸ch kÒ Ke(v), v V.  §Çu ra: Víi mçi ®Ønh v V chØ sè NR [v] tho¶ m·n: Víi mäi cung (u, v) cña ®å thÞ ta ®Òu cã NR[u] < NR[v]. Nguyễn Đức Nghĩa Toán rời rạc, Fall 2005 Bài toán đường đi ngắn nhất 42
  43. Thuật toán đánh số đỉnh procedure Numbering; begin for v V do Vao[v] := 0; for u V do (* TÝnh Vao[v] = b¸n bËc vµo cña v *) for v Ke(u) do Vao[v] := Vao[v] + 1 ; QUEUE :=  ; for v V do if Vao[v] = 0 then QUEUE  v ; num := 0; while QUEUE  do begin u  QUEUE ; num := num + 1 ; NR[u] := num ; for v Ke(u) do begin Vao[v] := Vao[v] - 1 ; if Vao[v] = 0 then QUEUE  v ; end; end; end; Nguyễn Đức Nghĩa Toán rời rạc, Fall 2005 Bài toán đường đi ngắn nhất 43
  44. Thuật toán đánh số đỉnh Râ rµng trong bíc khëi t¹o ta ph¶i duyÖt qua tÊt c¶ c¸c cung cña ®å thÞ khi tÝnh b¸n bËc vµo cña c¸c ®Ønh, v× vËy ë ®ã ta tèn cì O(m) phÐp to¸n, trong ®ã m lµ sè cung cña ®å thÞ. TiÕp theo, mçi lÇn ®¸nh sè mét ®Ønh, ®Ó thùc hiÖn viÖc lo¹i bá ®Ønh ®· ®¸nh sè cïng víi c¸c cung ®i ra khái nã, chóng ta l¹i duyÖt qua tÊt c¶ c¸c cung nµy. Suy ra ®Ó ®¸nh sè tÊt c¶ c¸c ®Ønh cña ®å thÞ chóng ta sÏ ph¶i duyÖt qua tÊt c¶ c¸c cung cña ®å thÞ mét lÇn n÷a. VËy ®é phøc t¹p cña thuËt to¸n lµ O(m). Nguyễn Đức Nghĩa Toán rời rạc, Fall 2005 Bài toán đường đi ngắn nhất 44
  45. Thuật toán tìm đđnn trên đồ thị không có chu trình  Do cã thuËt to¸n ®¸nh sè trªn, nªn khi xÐt ®å thÞ kh«ng cã chu tr×nh ta cã thÓ gi¶ thiÕt lµ c¸c ®Ønh cña nã ®îc ®¸nh sè sao cho mçi cung chØ ®i tõ ®Ønh cã chØ sè nhá ®Õn ®Ønh cã chØ sè lín h¬n.  ThuËt to¸n t×m ®êng ®i ng¾n nhÊt tõ ®Ønh nguån v[1] ®Õn tÊt c¶ c¸c ®Ønh cßn l¹i trªn®å thÞ kh«ng cã chu tr×nh  §Çu vµo: §å thÞ G=(V, E), trong ®ã V={ v[1], v[2], , v[n] }. §èi víi mçi cung (v[i], v[j]) E, ta cã i < j. §å thÞ ®îc cho bëi danh s¸ch kÒ Ke(v) , v V.  §Çu ra: Kho¶ng c¸ch tõ v[1] ®Õn tÊt c¶ c¸c ®Ønh cßn Nguyễn Đứcl¹i Nghĩa Toán rời rạc, Fall 2005 Bài toán đường đi ngắn nhất 45 ®îc ghi trong m¶ng d[v[i]], i = 2, 3, , n
  46. Thuật toán tìm đđnn trên đồ thị không có chu trình procedure Critical_Path; begin d[v[1]] := 0; for j:=1 to n do d[v[j]] :=∞; for v[j] Ke[v[1]] do d[v[j]] := w(v[1], v[j]) ; for j:= 2 to n do for v Ke[v[j]] do d[v] := min ( d[v], d[v[j]] + w(v[j], v) ) ; end;  §é phøc t¹p tÝnh to¸n cña thuËt to¸n lµ O(m), do mçi cung cña ®å thÞ ph¶i xÐt qua ®óng mét lÇn. Nguyễn Đức Nghĩa Toán rời rạc, Fall 2005 Bài toán đường đi ngắn nhất 46
  47. Ví dụ Cần tìm đường đi ngắn nhất từ s đến tất cả các đỉnh đạt đến được từ nó 6 1 r s t u v w 5 2 7 –1 –2 0 4 3 2 Nguyễn Đức Nghĩa Comp 122, Fall 2003 Single-source SPs - 47
  48. Ví dụ 6 1 r s t u v w 5 2 7 –1 –2 0 4 3 2 Nguyễn Đức Nghĩa Comp 122, Fall 2003 Single-source SPs - 48
  49. Ví dụ 6 1 r s t u v w 5 2 7 –1 –2 0 2 6 4 3 2 Nguyễn Đức Nghĩa Comp 122, Fall 2003 Single-source SPs - 49
  50. Ví dụ 6 1 r s t u v w 5 2 7 –1 –2 0 2 6 6 4 4 3 2 Nguyễn Đức Nghĩa Comp 122, Fall 2003 Single-source SPs - 50
  51. Ví dụ 6 1 r s t u v w 5 2 7 –1 –2 0 2 6 5 4 4 3 2 Nguyễn Đức Nghĩa Comp 122, Fall 2003 Single-source SPs - 51
  52. Ví dụ 6 1 r s t u v w 5 2 7 –1 –2 0 2 6 5 3 4 3 2 Nguyễn Đức Nghĩa Comp 122, Fall 2003 Single-source SPs - 52
  53. Ví dụ 6 1 r s t u v w 5 2 7 –1 –2 0 2 6 5 3 4 3 2 Kết quả: Cây đường đi ngắn nhất từ s thể hiện bởi các cung màu đỏ Nguyễn Đức Nghĩa Comp 122, Fall 2003 Single-source SPs - 53
  54. Ứng dụng: PERT  X©y dùng ph¬ng ph¸p gi¶i bµi to¸n ®iÒu khiÓn viÖc thùc hiÖn nh÷ng dù ¸n lín, gäi t¾t lµ PERT (Project Evaluation and Review Technique) hay CDM (Critical path Method). ViÖc thi c«ng mét c«ng tr×nh lín ®îc chia ra lµm n c«ng ®o¹n, ®¸nh sè tõ 1 ®Õn n. Cã mét sè c«ng ®o¹n mµ viÖc thùc hiÖn nã chØ ®îc tiÕn hµnh sau khi mét sè c«ng ®o¹n nµo ®ã ®· hoµn thµnh. §èi víi mçi c«ng ®o¹n i biÕt t[i] lµ thêi gian cÇn thiÕt ®Ó hoµn thµnh nã (i = 1, 2, , n). Nguyễn Đức Nghĩa Toán rời rạc, Fall 2005 Bài toán đường đi ngắn nhất 54
  55. Ứng dụng: PERT  C¸c d÷ liÖu víi n = 8 ®îc cho trong b¶ng sau ®©y Công đoạn t[i] Các công đoạn phải hoàn thành trước nó 1 15 Không có 2 30 1 3 80 Không có 4 45 2, 3 5 124 4 6 15 2, 3 7 15 5, 6 8 19 5 Nguyễn Đức Nghĩa Toán rời rạc, Fall 2005 Bài toán đường đi ngắn nhất 55
  56. Ứng dụng: PERT  Bµi to¸n PERT: Gi¶ sö thêi ®iÓm b¾t ®Çu tiÕn hµnh thi c«ng c«ng tr×nh lµ 0. H·y t×m tiÕn ®é thi c«ng c«ng tr×nh (chØ râ mçi c«ng ®o¹n ph¶i ®îc b¾t ®Çu thc hiÖn vµo thêi ®iÓm nµo) ®Ó cho c«ng tr×nh ®îc hoµn thµnh xong trong thêi ®iÓm sím nhÊt cã thÓ ®îc.  Ta cã thÓ x©y dùng ®å thÞ cã híng n ®Ønh biÓu diÔn rµng buéc vÒ tr×nh tù thùc hiÖc c¸c c«ng viÖc nh sau: • Mçi ®Ønh cña ®å thÞ t¬ng øng víi mét c«ng viÖc. • NÕu c«ng viÖc i ph¶i ®îc thùc hiÖn tríc c«ng ®o¹n j th× trªn ®å thÞ cã cung (i,j), träng sè trªn cung nµy ®- îc g¸n b»ng t[i] Nguyễn Đức Nghĩa Toán rời rạc, Fall 2005 Bài toán đường đi ngắn nhất 56
  57. Thuật toán PERT  Thªm vµo ®å thÞ 2 ®Ønh 0 vµ n+1 t¬ng øng víi hai sù kiÖn ®Æc biÖt: • ®Ønh sè 0 t¬ng øng víi c«ng ®o¹n LÔ khëi c«ng, nã ph¶i ®îc thùc hiÖn tríc tÊt c¶ c¸c c«ng ®o¹n kh¸c, vµ • ®Ønh n+1 t¬ng øng víi c«ng ®o¹n C¾t b¨ng kh¸nh thµnh c«ng tr×nh, nã ph¶i thùc hiÖn sau tÊt c¶ c¸c c«ng ®o¹n, • víi t[0] = t[n+1] = 0 (trªn thùc tÕ chØ cÇn nèi ®Ønh 0 víi tÊt c¶ c¸c ®Ønh cã b¸n bËc vµo b»ng 0 vµ nèi tÊt c¶ c¸c ®Ønh cã b¸n bËc ra b»ng 0 víi ®Ønh n+1). Gäi ®å thÞ thu ®îc lµ G.  Râ rµng bµi to¸n ®Æt ra dÉn vÒ bµi to¸n t×m ®êng ®i dµi nhÊt tõ ®Ønh 0 ®Õn tÊt c¶ c¸c ®Ønh cßn l¹i trªn ®å thÞ Nguyễn ĐứcG. Nghĩa Toán rời rạc, Fall 2005 Bài toán đường đi ngắn nhất 57
  58. Thuật toán PERT  Do ®å thÞ G kh«ng chøa chu tr×nh, nªn ®Ó gi¶i bµi to¸n ®Æt ra cã thÓ ¸p dông thuËt to¸n Critical_Path trong ®ã chØ cÇn ®æi to¸n tö min thµnh to¸n tö max.  KÕt thóc thuËt to¸n, ta thu ®îc d[v] lµ ®é dµi ®- êng ®i dµi nhÊt tõ ®Ønh 0 ®Õn ®Ønh v.  Khi ®ã d[v] cho ta thêi ®iÓm sím nhÊt cã thÓ b¾t ®Çu thùc hiÖn c«ng ®o¹n v, nãi riªng d[n+1] lµ thêi ®iÓm sím nhÊt cã thÓ c¾t b¨ng kh¸nh thµnh, tøc lµ thêi ®iÓm sím nhÊt cã thÓ hoµn thµnh toµn bé c«ng tr×nh. Nguyễn Đức Nghĩa Toán rời rạc, Fall 2005 Bài toán đường đi ngắn nhất 58
  59. PERT: Ví dụ minh hoạ  Qui bài toán PERT về tìm đường đi dài nhất trên đồ thị không có chu trình 0 15 80 129 15 30 1 2 6 8 0 19 148 80 4 0 0 9 30 15 0 15 3 4 5 7 80 45 4 0 80 125 129 Nguyễn Đức Nghĩa Toán rời rạc, Fall 2005 Bài toán đường đi ngắn nhất 59
  60. Nội dung 5.1. Bài toán đường đi ngắn nhất (ĐĐNN) 5.2. Tính chất của ĐĐNN, Giảm cận trên 5.3. Thuật toán Bellman-Ford 5.4. Thuật toán Dijkstra 5.5. Đường đi ngắn nhất trong đồ thị không có chu trình 5.6. Thuật toán Floyd-Warshal Nguyễn Đức Nghĩa Toán rời rạc, Fall 2005 Bài toán đường đi ngắn nhất 60
  61. ĐƯỜNG ĐI NGẮN NHẤT GIỮA MỌI CẶP ĐỈNH All-Pairs Shortest Paths Nguyễn Đức Nghĩa Toán rời rạc, Fall 2005 Bài toán đường đi ngắn nhất 61
  62. Đường đi ngắn nhất giữa mọi cặp đỉnh Bài toán Cho đồ thị G = (V, E), với trọng số trên cạnh e là w(e), đối với mỗi cặp đỉnh u, v trong V, tìm đường đi ngắn nhất từ u đến v. Đầu vào: ma trận trọng số. Đầu ra ma trận: phần tử ở dòng u cột v là độ dài đường đi ngắn nhất từ u đến v. Cho phép có trọng số âm Giả thiết: Đồ thị không có chu trình âm. Nguyễn Đức Nghĩa Toán rời rạc, Fall 2005 Bài toán đường đi ngắn nhất 62
  63. Ví dụ Đầu vào 2 3 4 n n ma trận W = (w ) với 8 ij 1 3 0 nếu i = j w (i, j) nếu i j & (i, j) E 7 1 wij = -4 2 -5 còn lại 0 3 8 -4 5 4 6 0 1 7 4 0 2 -5 0 6 0 Nguyễn Đức Nghĩa Toán rời rạc, Fall 2005 Bài toán đường đi ngắn nhất 63
  64. Tiếp Đầu ra 2 4 3 Đường đi: 1- 5 - 4 - 3 - 2 = – 4 + 6 – 5 + 4 1 8 3 0 1 -3 2 -4 7 1 -4 2 -5 3 0 -4 1 -1 7 4 0 5 3 5 4 2 -1 -5 0 -2 6 8 5 1 6 0 4 - 1- 5 5 - 4 - 1 Nguyễn Đức Nghĩa Toán rời rạc, Fall 2005 Bài toán đường đi ngắn nhất 64
  65. Thuật toán Floyd-Warshall (m) độ dài đường đi ngắn nhất từ i đến j sử dụng các đỉnh trung gian dij = trong tập đỉnh { 1, 2, , m }. i m m m j (n) Khi đó độ dài đường đi ngắn nhất từ i đến j là dij Nguyễn Đức Nghĩa Toán rời rạc, Fall 2005 Bài toán đường đi ngắn nhất 65
  66. Công thức đệ qui tính d(h) (0) dij = wij i j d (h) = min ( d (h-1), d (h-1)+ d (h-1)) nếu h 1 ij ij ih hj (h-1) d (h-1) dih h hj i j (h-1) dij Nguyễn Đức Nghĩa Toán rời rạc, Fall 2005 Bài toán đường đi ngắn nhất 66
  67. Thuật toán Floyd-Warshall Floyd-Warshall(n, W) D(0)  W for k  1 to n do for i  1 to n do for j  1 to n do (k) (k-1) (k-1) (k-1) dij  min (dij , d ik + d kj ) return D(n) Thời gian tính (n3) ! Nguyễn Đức Nghĩa Toán rời rạc, Fall 2005 Bài toán đường đi ngắn nhất 67
  68. Xây dựng đường đi ngắn nhất (k) (k) Predecessor matrix P = (p ij ) : (k) i pij j đường đi ngắn nhất từ i đến j chỉ qua các đỉnh trung gian trong {1, 2, , k}. i, nếu (i, j) E (0) pij = NIL, nếu (i, j) E (k-1) (k-1) (k-1) (k-1) p nếu d d + d i p(k) = ij ij ik kj j ij (k-1) k pkj trái lại Nguyễn Đức Nghĩa Toán rời rạc, Fall 2005 Bài toán đường đi ngắn nhất 68
  69. Ví dụ 3 D (0) 0 3 5 1 2 0 1 6 0 2 5 1 6 4 0 (0) NIL 1 1 NIL 3 2 4 P NIL NIL 2 2 4 NIL NIL NIL 3 4 NIL NIL NIL Có thể sử dụng 1 là đỉnh trung gian: 0 3 5 (1) NIL 1 1 NIL D (1) P 0 1 6 NIL NIL 2 2 0 2 NIL NIL NIL 3 4 7 9 0 4 1 1 NIL Nguyễn Đức Nghĩa Toán rời rạc, Fall 2005 Bài toán đường đi ngắn nhất 69
  70. Ví dụ (tiếp) (2) 0 3 4 9 (2) NIL 1 2 2 D P 0 1 6 NIL NIL 2 2 0 2 NIL NIL NIL 3 4 7 8 0 4 1 2 NIL 0 3 4 6 NIL 1 2 3 (3) (3) D 0 1 3 P NIL NIL 2 3 0 2 NIL NIL NIL 3 4 7 8 0 4 1 2 NIL NIL 1 2 3 0 3 4 6 (4) (4) D 7 0 1 3 P 4 NIL 2 3 6 9 0 2 4 1 NIL 3 4 7 8 0 4 1 2 NIL Nguyễn Đức Nghĩa Toán rời rạc, Fall 2005 Bài toán đường đi ngắn nhất 70
  71. Ví dụ (tiếp) 3 2 4 1 2 3 4 1 3 1 2 4 3 1 2 3 3 4 1 2 3 1 2 2 1 2 3 4 3 4 Nguyễn Đức Nghĩa Toán rời rạc, Fall 2005 Bài toán đường đi ngắn nhất 71
  72. Thuật toán Floyd-Warshall Floyd-Warshall(n, W) D  W for k  1 to n do for i  1 to n do for j  1 to n do dij  min (dij , dik + dkj) return D Thời gian tính (n3) ! Nguyễn Đức Nghĩa Toán rời rạc, Fall 2005 Bài toán đường đi ngắn nhất 72
  73. Robert W. Floyd, 1936-2001  Born in New York, Floyd finished school at age 14. At the University of Chicago, he received a Bachelor's degree in liberal arts in 1953 (when still only 17) and a second Bachelor's degree in physics in 1958.  Becoming a computer operator in the early 1960s, he began publishing many noteworthy papers and was appointed an associate professor at Carnegie Mellon University by the time he was 27 and became a full professor at Stanford University six years later. He obtained this position without a Ph.D.  Turing Award, 1978. 73 Nguyễn Đức Nghĩa 2007/4/2 All-pairs distance
  74. Stephen Warshall  1935 – 2006  Proving the correctness of the transitive closure algorithm for boolean circuit. • (Wikipedia) There is an interesting anecdote about his proof that the transitive closure algorithm, now known as Warshall's algorithm, is correct. He and a colleague at Technical Operations bet a bottle of rum on who first could determine whether this algorithm always works. Warshall came up with his proof overnight, winning the bet and the rum, which he shared with the loser of the bet. Because Warshall did not like sitting at a desk, he did much of his creative work in unconventional places such as on a sailboat in the Indian Ocean or in a Greek lemon orchard. 74 Nguyễn Đức Nghĩa 2007/4/2 All-pairs distance
  75. Questions? Nguyễn Đức Nghĩa Toán rời rạc, Fall 2005 Bài toán đường đi ngắn nhất 75
  76. Bao đóng truyền ứng (Transitive Closure) Bao đóng truyền ứng của đồ thị G = (V, E) là G* = (V, E*) sao cho (i, j) E* iff có đường đi từ i đến j trên G. G: G*: 1 1 5 2 5 2 4 3 4 3 Nguyễn Đức Nghĩa Toán rời rạc, Fall 2005 Bài toán đường đi ngắn nhất 76
  77. Thuật toán Floyd-Warshall Ma trận xuất phát là ma trận kề 1 nếu i = j hoặc có cạnh nối 2 đỉnh i và j a (i , j) = 0 trái lại i j Nếu Thuật toán Floyd-Warshall thay AND AND x y min boolean OR i OR j + boolean AND OR Thời gian tính (n3 ) Nguyễn Đức Nghĩa Toán rời rạc, Fall 2005 Bài toán đường đi ngắn nhất 77
  78. Questions? Nguyễn Đức Nghĩa Toán rời rạc, Fall 2005 Bài toán đường đi ngắn nhất 78