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

Toán rời rạc, Fall 2005 Bài toán đường đi ngắn nhất 1Chương 5BÀI TOÁN ĐƯỜNG ĐI NGẮN NHẤTToán rời rạc, Fall 2005 Bài toán đường đi ngắn nhất 2Nội dung5.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ên5.3. Thuật toán Bellman-Ford5.4. Thuật toán Dijkstra5.5. Đường đi ngắn nhất trong đồ thị không có chu trình5.6. Thuật toán Floyd-WarshalToán rời rạc, Fall 2005 Bài toán đường đi ngắn nhất 35.1. Bài toán đường đi ngắn nhấtCho đơ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ốĐườ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).Toán rời rạc, Fall 2005 Bài toán đường đi ngắn nhất 4Ví dụpath s s,a s,a,b s,a,b,c s,a,d s,a,b,e s,a,b,e,fweight 0 3 4 6 6 6 9 s a b c d e fCho đồ 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. asbefdc335122241635đỉnh nguồnToán rời rạc, Fall 2005 Bài toán đường đi ngắn nhất 5Cá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 imagingGiải các bài toán phức tạp hơn trên mạng...Toán rời rạc, Fall 2005 Bài toán đường đi ngắn nhất 6Các dạng bài toán ĐĐNNBà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.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.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. Toán rời rạc, Fall 2005 Bài toán đường đi ngắn nhất 7Nhận xétCác bài toán được xếp theo thứ tự từ đơn giản đến phức tạpHễ 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ạiToán rời rạc, Fall 2005 Bài toán đường đi ngắn nhất 8Giả thiết cơ bảnNếu đồ thị có chu trình âm thì độ dài đường đi giữa hai đỉnh nào đó có thể làm nhỏ tuỳ ý:-18abecd2355Giả thiết: Đồ thị không chứa chu trình độ dài âm (gọi tắt là chu trình âm) Xét đường đi từ a đến e:P: a (d  b c d)  ew(P) = 7-10  -∞, khi  + ∞Toán rời rạc, Fall 2005 Bài toán đường đi ngắn nhất 9Trọng số âm-603511-1- -- 3523784-46-3sacebdfg2-83hjikhông đạt tới được từ schu trình âmđỉnhnguồnĐộ dài của đường đi ngắn nhất có thể là  hoặc – . Toán rời rạc, Fall 2005 Bài toán đường đi ngắn nhất 105.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ên5.3. Thuật toán Bellman-Ford5.4. Thuật toán Dijkstra5.5. Đường đi ngắn nhất trong đồ thị không có chu trình5.6. Thuật toán Floyd-WarshalToán rời rạc, Fall 2005 Bài toán đường đi ngắn nhất 11Các tính chất của ĐĐNNTí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ó.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 1uvCw(C)  0Toán rời rạc, Fall 2005 Bài toán đường đi ngắn nhất 12Các tính chất của ĐĐNNTí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 đượcP’ij là đường đi từ vi đến vj thoả mãn w(P’ij) d[u] + w(u, v)Relax(u, v) if d[v] > d[u] + w(u, v) then d[v]  d[u] + w(u, v) p[v]  uCá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 chúng để thực hiện giảm cận. Toán rời rạc, Fall 2005 Bài toán đường đi ngắn nhất 17Nhậ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¸nNhË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 ch­a 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.Toán rời rạc, Fall 2005 Bài toán đường đi ngắn nhất 18Nội dung5.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ên5.3. Thuật toán Bellman-Ford5.4. Thuật toán Dijkstra5.5. Đường đi ngắn nhất trong đồ thị không có chu trình5.6. Thuật toán Floyd-WarshalThuật toán Ford-Bellman Toán rời rạc, Fall 2005 Bài toán đường đi ngắn nhất 19Richard Bellman1920-1984Lester R. Ford, Jr. 1927~Toán rời rạc, Fall 2005 Bài toán đường đi ngắn nhất 20Thuật toán Ford-BellmanThuË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  Vd[v] = (s, v);p[v] - ®Ønh ®i tr­íc v trong ®®nn tõ s ®Õn v.Toán rời rạc, Fall 2005 Bài toán đường đi ngắn nhất 21Mô tả thuật toánprocedure 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; Toán rời rạc, Fall 2005 Bài toán đường đi ngắn nhất 22Nhận xétTÝ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 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).Toán rời rạc, Fall 2005 Bài toán đường đi ngắn nhất 30Nội dung5.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ên5.3. Thuật toán Bellman-Ford5.4. Thuật toán Dijkstra5.5. Đường đi ngắn nhất trong đồ thị không có chu trình5.6. Thuật toán Floyd-WarshalToán rời rạc, Fall 2005 Bài toán đường đi ngắn nhất 31Thuật toán DijkstraTrong 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 gán nhãn. Thoạt tiên nh·n của các đỉnh là t¹m 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.Edsger W.Dijkstra(1930-2002)Toán rời rạc, Fall 2005 Bài toán đường đi ngắn nhất 32Thuậ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  Vd[v] = (s, v);p[v] - ®Ønh ®i tr­íc v trong ®®nn tõ s ®Õn v.Toán rời rạc, Fall 2005 Bài toán đường đi ngắn nhất 33Thuật toán Dijkstraprocedure Dijkstra; 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; end; end; Tập S: Chỉ cần cho chứng minh định lýToán rời rạc, Fall 2005 Bài toán đường đi ngắn nhất 34Thuậ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)Toán rời rạc, Fall 2005 Bài toán đường đi ngắn nhất 35Chứng minh tính đúng đắn của Thuật toán DijkstraTa sẽ CM với mỗi v  S, d(v) = (s, v).Qui nạp theo |S|.Cơ sở qui nạp: Với |S| = 1, rõ ràng là đúng.Chuyển qui nạp:giả sử thuật toán Dijkstra bổ sung v vào Sd(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 vP* 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  d(y) theo thuật toánvì thế thuật toán Dijkstra phải chọn y thay vì chọn v ?!SsyvxP*Toán rời rạc, Fall 2005 Bài toán đường đi ngắn nhất 36Ví dụĐỉnh 1Đỉnh 2Đỉnh 3Đỉnh 4Đỉnh 5Đỉnh 6Khởi tạo[0, 1][1, 1]*[, 1][, 1][, 1][, 1]1 --[6, 2][3, 2]*[, 1][8, 2]2 --[4, 4]*-[7, 4][8, 2]3----[6, 3][5, 3]*4----[6, 3]*-5------Tìm đường đi ngắn nhất từ đỉnh 1 đến tất cả các đỉnh còn lại112211075431234652Toán rời rạc, Fall 2005 Bài toán đường đi ngắn nhất 37Cây đường đi ngắn nhấtTậ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.11221107543123465214356 Các cạnh màu đỏ tạo thành cây đđnn xuất phát từ đỉnh 1 Số màu đỏ viết bên cạnh mỗi đỉnh là độ dài đường đi ngắn nhất từ 1 đến nó.Toán rời rạc, Fall 2005 Bài toán đường đi ngắn nhất 38Nội dung5.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ên5.3. Thuật toán Bellman-Ford5.4. Thuật toán Dijkstra5.5. Đường đi ngắn nhất trong đồ thị không có chu trình5.6. Thuật toán Floyd-WarshalToán rời rạc, Fall 2005 Bài toán đường đi ngắn nhất 39Đường đi trong đồ thị không có chu trìnhShortest Paths In Directed Acyclic GraphsToán rời rạc, Fall 2005 Bài toán đường đi ngắn nhất 40Đường đi trong đồ thị không có chu trìnhMé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 .Toán rời rạc, Fall 2005 Bài toán đường đi ngắn nhất 41Thuật toán đánh số đỉnhTr­í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è. Toán rời rạc, Fall 2005 Bài toán đường đi ngắn nhất 42Thuậ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]. Toán rời rạc, Fall 2005 Bài toán đường đi ngắn nhất 43Thuật toán đánh số đỉnhprocedure 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; Toán rời rạc, Fall 2005 Bài toán đường đi ngắn nhất 44Thuật toán đánh số đỉnhRâ 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).Toán rời rạc, Fall 2005 Bài toán đường đi ngắn nhất 45Thuật toán tìm đđnn trên đồ thị không có chu trìnhDo 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 l¹i ®­îc ghi trong m¶ng d[v[i]], i = 2, 3, ..., n Toán rời rạc, Fall 2005 Bài toán đường đi ngắn nhất 46Thuật toán tìm đđnn trên đồ thị không có chu trìnhprocedure 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.Comp 122, Fall 2003 Single-source SPs - 47Ví dụ0rstuvw527–1–261324Cần tìm đường đi ngắn nhất từ s đến tất cả các đỉnh đạt đến được từ nó Comp 122, Fall 2003 Single-source SPs - 48Ví dụ0rstuvw527–1–261324Comp 122, Fall 2003 Single-source SPs - 49Ví dụ026rstuvw527–1–261324Comp 122, Fall 2003 Single-source SPs - 50Ví dụ02664rstuvw527–1–261324Comp 122, Fall 2003 Single-source SPs - 51Ví dụ02654rstuvw527–1–261324Comp 122, Fall 2003 Single-source SPs - 52Ví dụ02653rstuvw527–1–261324Comp 122, Fall 2003 Single-source SPs - 53Ví dụ02653rstuvw527–1–261324Kết quả: Cây đường đi ngắn nhất từ s thể hiện bởi các cung màu đỏToán rời rạc, Fall 2005 Bài toán đường đi ngắn nhất 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). Toán rời rạc, Fall 2005 Bài toán đường đi ngắn nhất 55Ứng dụng: PERT C¸c d÷ liÖu víi n = 8 ®­îc cho trong b¶ng sau ®©yCông đoạnt[i]Các công đoạn phải hoàn thành trước nó115Không có2301380Không có4452, 3512446152, 37155, 68195Toán rời rạc, Fall 2005 Bài toán đường đi ngắn nhất 56Ứng dụng: PERTBµ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 th­c 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] Toán rời rạc, Fall 2005 Bài toán đường đi ngắn nhất 57Thuật toán PERTThª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Þ G. Toán rời rạc, Fall 2005 Bài toán đường đi ngắn nhất 58Thuậ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.Toán rời rạc, Fall 2005 Bài toán đường đi ngắn nhất 59PERT: 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ình30308080150154453124650097841519012912580801501291480Toán rời rạc, Fall 2005 Bài toán đường đi ngắn nhất 60Nội dung5.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ên5.3. Thuật toán Bellman-Ford5.4. Thuật toán Dijkstra5.5. Đường đi ngắn nhất trong đồ thị không có chu trình5.6. Thuật toán Floyd-WarshalToán rời rạc, Fall 2005 Bài toán đường đi ngắn nhất 61ĐƯỜNG ĐI NGẮN NHẤT GIỮA MỌI CẶP ĐỈNHAll-Pairs Shortest PathsToán rời rạc, Fall 2005 Bài toán đường đi ngắn nhất 62Đường đi ngắn nhất giữa mọi cặp đỉnhBà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 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ố âmGiả thiết: Đồ thị không có chu trình âm. Đầu vào: ma trận trọng số. Toán rời rạc, Fall 2005 Bài toán đường đi ngắn nhất 63Ví dụ215343482-5167-4Đầu vào0 3 8  -4  0  1 7 4 0  2  -5 0    6 0n  n ma trận W = (w ) với ijw =0 nếu i = jw (i, j) nếu i  j & (i, j)  E còn lạiijToán rời rạc, Fall 2005 Bài toán đường đi ngắn nhất 64Tiếp215343482-5167-40 1 -3 2 -43 0 -4 1 -17 4 0 5 32 -1 -5 0 -28 5 1 6 05 - 4 - 1Đường đi: 1- 5 - 4 - 3 - 24 - 1- 5Đầu ra= – 4 + 6 – 5 + 4Toán rời rạc, Fall 2005 Bài toán đường đi ngắn nhất 65Thuật toán Floyd-Warshalld = độ dài đường đi ngắn nhất từ i đến j sử dụng các đỉnh trung gian trong tập đỉnh { 1, 2, , m }. ij (m)...ij m  m  mKhi đó độ dài đường đi ngắn nhất từ i đến j là d ij (n)Toán rời rạc, Fall 2005 Bài toán đường đi ngắn nhất 66Công thức đệ qui tính d(h)ijd = w ij ij(0)d = min ( d , d + d ) nếu h  1 (h) (h-1) (h-1) (h-1)ij ij ih hjijhd(h-1)ijd(h-1)ihd(h-1)hjToán rời rạc, Fall 2005 Bài toán đường đi ngắn nhất 67Thuật toán Floyd-WarshallFloyd-Warshall(n, W) D(0)  W for k  1 to n do for i  1 to n do for j  1 to n do d  min (d , d + d ) return D(n) (k) (k-1) (k-1) (k-1)Thời gian tính (n3) !ij ik kjijToán rời rạc, Fall 2005 Bài toán đường đi ngắn nhất 68Xây dựng đường đi ngắn nhấtPredecessor matrix P = (p ) : ij(k)đườ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 NIL, nếu (i, j)  E p = (k)ijp nếu d  d + d ijij(k-1) ikkj(k-1)(k-1) (k-1)p trái lại(k-1)kj(k)ijkp = ij(0)ijp(k)ijToán rời rạc, Fall 2005 Bài toán đường đi ngắn nhất 69Ví dụ1342451362D (0) 0 3 5   0 1 6   0 2 4   0P(0)NIL 1 1 NILNIL NIL 2 2NIL NIL NIL 3 4 NIL NIL NILD (1) 0 3 5   0 1 6   0 2 4 7 9 0P(1)NIL 1 1 NILNIL NIL 2 2NIL NIL NIL 3 4 1 1 NILCó thể sử dụng 1 là đỉnh trung gian:Toán rời rạc, Fall 2005 Bài toán đường đi ngắn nhất 70Ví dụ (tiếp)D (2) 0 3 4 9  0 1 6   0 2 4 7 8 0P(2)NIL 1 2 2NIL NIL 2 2NIL NIL NIL 3 4 1 2 NILD 0 3 4 6  0 1 3   0 2 4 7 8 0(3)P(3)NIL 1 2 3NIL NIL 2 3NIL NIL NIL 3 4 1 2 NIL(4)D 0 3 4 6 7 0 1 3 6 9 0 2 4 7 8 0P(4)NIL 1 2 3 4 NIL 2 3 4 1 NIL 3 4 1 2 NILToán rời rạc, Fall 2005 Bài toán đường đi ngắn nhất 71Ví dụ (tiếp)312122211133334443331412222443Toán rời rạc, Fall 2005 Bài toán đường đi ngắn nhất 72Thuật toán Floyd-WarshallFloyd-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 DThời gian tính (n3) !2007/4/2All-pairs distance73Robert W. Floyd, 1936-2001Born 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.2007/4/2All-pairs distance74Stephen Warshall1935 – 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.Toán rời rạc, Fall 2005 Bài toán đường đi ngắn nhất 75 Questions?Toán rời rạc, Fall 2005 Bài toán đường đi ngắn nhất 76Bao đó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. 5342113425G: G*:Toán rời rạc, Fall 2005 Bài toán đường đi ngắn nhất 77Thuật toán Floyd-WarshallMa trận xuất phát là ma trận kề Thuật toán Floyd-Warshall thaymin boolean OR + boolean ANDThời gian tính (n )3 1 nếu i = j hoặc có cạnh nối 2 đỉnh i và j a (i , j) = 0 trái lạiANDANDORORiyxjjiNếuToán rời rạc, Fall 2005 Bài toán đường đi ngắn nhất 78 Questions?