Bài giảng Toán rời rạc (Phần II: Lý thuyết đồ thị): Chương 5 - Nguyễn Đức Nghĩa

Chương 5 trang bị cho người học những kiến thức cơ bản về bài toán đường đi ngắn nhất. Thông qua chương này người học có thể hiểu được: Bài toán đường đi ngắn nhất (ĐĐNN); tính chất của ĐĐNN, giảm cận trên; thuật toán Bellman-Ford; thuật toán Dijkstra; đường đi ngắn nhất trong đồ thị không có chu trình; thuật toán Floyd-Warshal.
Nội dung trích xuất từ tài liệu:
Bài giảng Toán rời rạc (Phần II: Lý thuyết đồ thị): Chương 5 - Nguyễn Đức Nghĩa Chương5 BÀITOÁNĐƯỜNGĐINGẮNNHẤTNguyễnĐứcNghĩa Toánrờirạc,Fall2005 Bàitoánđườngđingắnn Nộidung 5.1.Bàitoánđườngđingắnnhất(ĐĐNN) 5.2.TínhchấtcủaĐĐNN,Giảmcậntrên 5.3.ThuậttoánBellmanFord 5.4.ThuậttoánDijkstra 5.5.Đườngđingắnnhấttrongđồthịkhôngcóchutrình 5.6.ThuậttoánFloydWarshalNguyễnĐứcNghĩa Toánrờirạc,Fall2005 Bàitoánđườngđingắnn 5.1.Bàitoánđườngđingắnnhất  Chođơnđồthịcóhướng G=(V,E)vớihàmtrọngsố w:E R(w(e)đượcgọilàđộdàihaytrọngsốcủa cạnhe)  ĐộdàicủađườngđiP=v1 v2 … vklàsố k −1 w( P ) = w(vi , vi +1 ) i =1  Đườngđingắnnhấttừđỉnhuđếnđỉnhvlàđườngđi cóđộdàingắnnhấttrongsốcácđườngđinối uvới v.  Độdàicủađườngđingắnnhấttừ uđến vcònđược gọilàkhoảngcáchtừutớivvàkýhiệulà (u,v).NguyễnĐứcNghĩa Toánrờirạc,Fall2005 Bàitoánđườngđingắnn Vídụ ChođồthịcótrọngsốG=(V,E),vàđỉnhnguồns V,hãytìm đườngđingắnnhấttừsđếnmỗiđỉnhcònlại. 3 a d 3 4 6 đỉnhnguồn 5 s 1 c 1 2 f 2 5 3 b e 2 sabcdef weight0346669 pathss,as,a,bs,a,b,cs,a,ds,a,b,es,a,b,e,fNguyễnĐứcNghĩa Toánrờirạc,Fall2005 Bàitoánđườngđingắnn Cácứngdụngthựctế  Giaothông(Transportation)  Truyềntintrênmạng(Networkrouting)(cầnhướng cácgóitinđếnđíchtrênmạngtheođườngnào?)  Truyềnthông(Telecommunications)  Speechinterpretation(bestinterpretationofaspoken sentence)  Điềukhiểnrobot(Robotpathplanning)  Medicalimaging  Giảicácbàitoánphứctạphơntrênmạng  ...NguyễnĐứcNghĩa Toánrờirạc,Fall2005 Bàitoánđườngđingắnn CácdạngbàitoánĐĐNN 1. Bàitoánmộtnguồnmộtđích:Chohaiđỉnh svàt,cầntìmđườngđingắnnhấttừsđếnt. 2. Bài toán một nguồn nhiều đích: Cho s là đỉnhnguồn,cầntìmđườngđingắnnhấttừs đếntấtcảcácđỉnhcònlại. 3. Bàitoánmọicặp: Tìmđườngđingắnnhất giữamọicặpđỉnhcủađồthị.  ĐườngđingắnnhấttheosốcạnhBFS.NguyễnĐứcNghĩa Toánrờirạc,Fall2005 Bàitoánđườngđingắnn Nhậnxét Cácbàitoánđượcxếptheothứtựtừđơngiản đếnphứctạp Hễ cóthuậttoánhiệuquả đểgiảimộttrong ba bài toán thì thuật toán đó cũng có thể sử dụngđểgiảihaibàitoáncònlạiNguyễnĐứcNghĩa Toánrờirạc,Fall2005 Bàitoánđườngđingắnn Giảthiếtcơbản  Nếuđồthịcóchutrìnhâmthìđộdàiđườngđigiữa haiđỉnhnàođócóthểlàmnhỏtuỳý: 18 b c Xétđườngđitừađếne: a 3 5 P:a (d b c d) e 2 5 w(P)=710 ∞,khi +∞ d e Giảthiết: Đồthịkhôngchứachutrìnhđộdàiâm(gọi tắtlàchutrìnhâm)NguyễnĐứcNghĩa Toánrờirạc,Fall2005 Bàitoánđườngđingắnn Trọngsốâm Độdàicủađườngđingắnnhấtcóthểlà hoặc– . a b 4 3 1 h i 3 4 2 đỉnh s c 6 d g nguồ ...