Bài giảng Phân tích thiết kế giải thuật - Chương 10: Single-Source Shortest Paths

Nội dung "Bài giảng Phân tích thiết kế giải thuật - Chương 10: Single-Source Shortest Paths" tập trung vào những kiến thức cơ bản nhất về những cách giải bài toán các đường đi ngắn nhất từ một đỉnh nguồn, biểu diễn các đường đi ngắn nhất. Mời các bạn tham khảo.
Nội dung trích xuất từ tài liệu:
Bài giảng Phân tích thiết kế giải thuật - Chương 10: Single-Source Shortest PathsSingleSourceShortestPaths Cácđườngđingắnnhấttừmộtđỉnhnguồnª Bàitoáncácđườngđingắnnhất:mộtsốthuậtngữ. Chomộtđồthịcótrọngsố,cóhướngG=(V,E),vớimộthàmtrọng sốw:E – Trọngsốcủamộtđườngđip= v0,v1,…,vk • w(p)= w(vi 1,vi) i=1…k – Trọngsốcủađườngđingắnnhất(shortestpathweight)từuđến p v (u,v)= min{w(p):uv} nếucóđườngđitừuđếnv cáctrườnghợpkhác – Đườngđingắnnhấttừuđến t vlàbấtkỳđườ v ngđipnàotừuđến vsaochow(p)= (u,v). 6 u 3 2 1 4 2 7 3 5 620.11.2004 x y 2 Cácđườngđingắnnhấttừmộtđỉnhnguồn(tiếp)ª Bàitoáncácđườngđingắnnhấttừmộtnguồnduynhất(Single sourceshortestpathsproblem): – ChođồthịG=(V,E)vàmộtđỉnhnguồns V. – Tìmđườngđingắnnhấttừsđếnmọiđỉnhv V. 6 s 3 2 1 4 2 7 3 5 620.11.2004 Ch.10:SingleSourceShortestPaths 3 Cạnhcótrọngsốâmª Giảthiết:Trọngsốcủacạnhcóthểâm – Chutrìnhcóthểcótrọngsốâm – Nếutồntạimộtchutrìnhcótrọngsốâmđếnđược(reachable)từ sthìtrọngsốcủađườngđingắnnhấtkhôngđượcđịnhnghĩa: khôngđườngđinàotừsđếnmộtđỉnhnằmtrênchutrìnhcóthểlà đườngđingắnnhất. 4 3 1 a b h i 3 4 2 s c 6 d g 5 8 0 5 11 8 3 3 2 3 7 e f j 6 sốtrongmỗiđỉnhlàtrọngsốđườngđingắnnhất từđỉnhnguồns.20.11.2004 Ch.10:SingleSourceShortestPaths 4 Cạnhcótrọngsốâm(tiếp) – Nếutồntạimộtchutrìnhcótrọngsốâmtrênmộtđườngđitừs đếnv,tađịnhnghĩa (s,v)= . – Trongvídụsau,cácđỉnhh,i,jkhôngđếnđượctừsnêncótrọng sốđườngđingắnnhấtlà (chứkhônglà mặcdùchúngnằm trênmộtchutrìnhcótrọngsốâm). a b 4 3 1 h i 3 4 2 s c 6 d g 5 8 0 5 11 8 3 3 2 3 7 e f j 620.11.2004 Ch.10:SingleSourceShortestPaths 5 Biểudiễncácđườngđingắnnhấtª ĐồthịG=(V,E) – Vớimọiđỉnhv,đỉnhcha(predecessor)củavlàmộtđỉnhkháchay làNIL. Duytrì [v],contrỏđếnđỉnhcha.Dùng đểsuyrađườngđi ngắnnhấttừsđếnv. – ĐồthịconG (V ,E )(predecessorsubgraph) • V ={v V: [v] NIL} {s} • E ={( [v],v) E:v V {s}} [v] v20.11.2004 Ch.10:SingleSourceShortestPaths 6 Biểudiễncácđườngđingắnnhất(tiếp)ª ChoG=(V,E)làmộtđồthịcóhướng,cótrọngsố; Gkhôngchứachutrìnhtrọngsốâmđếnđượctừđỉnhnguồns V. CâycácđườngđingắnnhấtvớigốctạislàđồthịcóhướngG’= (V’,E’),vớiV’ VvàE’ Esaocho 1.V’làtậpcácđỉnhđếnđược(reachable)từstrongG 2.G’làcâycógốcvớigố ...