Cấu trúc dữ liệu và giải thuật (phần 20)

Trong tài liệu này các bạn sẽ được làm rõ thuật toán này qua một số ví dụ để các bạn thực hành, hãy làm nó bạn sẽ hiểu Dijstra là gì, tại sao nó là kinh điển
Nội dung trích xuất từ tài liệu:
Cấu trúc dữ liệu và giải thuật (phần 20) ư ng i ng n nh t ng nhGi i thi u: Bài toán tìm ư ng i ng n nh t là bài thi. ư c ngtoán quan tr ng trong lý thuy td ng trong th c t : Giao thông, vi n thông…Bài toán chia làm 2 lo i: Tìm ư ng i ng n nh t gi a 1 c p nh: Cho 2 nh u,v thu c G, tìm ư ng i ng n nh t t u n v : D kstra Tìm ư ng i ng n nh t gi a t t c các c p nh: Tìm ư ng i ng n nh t t nh u n nh v, v i m i c p nh u,v thu c G: Floyd-Warshall Gi i thu t Dijkstra Gi thu DijkstraGi i thi u:- Gi i thu t Dijkstra gi i bài toán ư ng i ng n nh t ngu n ơn (Single Source Shortest Path) trên mt th có tr ng s c nh u không âm. nh ư ng i ng n nh t gi a 2 nh a,b cho trư c- Xác tv n :ng d ng gi i thu t cây bao trùm t i gi i quy t bài toán ư ng i ng n nh t cóthi u ư c không??? Gi i thu t D kstra Gi thu kstraNh n xét:- Gi i thu t gi i bài toán MST s không ng d ng ư c cho bài toán ư ng i ng n nh t.- Vì sao??- Vì v y c n ph i ch nh s a gi i thu t trên phù h p v i bài toán ư ng i ng n nh t Gi i thu t D kstra Gi thu kstraGi i thu t:- m i nh v, gi i thu t Dijkstra xác nh 3 thôngtin: kv,dv,pv kv = 0 ho c 1 – xác nh tr ng thái c a nh v ( 0 –• chưa ch n, 1 – ã ch n)• dv: Chi u dài ư ng i tìm th y t i th i i m ang xét t a n v• pv: là nh trư c c a nh v trên ư ng i ng n nh t t a b. ư ng i ng n nh t t a n b có d ng {a,…,pv,v,…,b} Gi i thu t D kstra Gi thu kstraB1: Kh i t o: kv=0,∀v∈V; dv= ∞,∀v ∈ V {a}; da=0.B2: Ch n v∈V sao cho kv=0 và dv = min {dt / t∈V,kt=0 } – N u dv = ∞ thì k t thúc, không t n t i ư ng i t a b.B3: ánh d u nh v, kv= 1.B4: N u v=b thì k t thúc và db là dài ư ng i ng n nh t t a b. Ngư c l i n u v ≠ b sang B5.B5: V i m i nh u k v i v mà ku = 0, ki m tra N u du > dv + w(v,u) thì du= dv + w(v,u) nh v: pu:= v. Quay l i B2. Ghi nh Gi i thu t D kstra Gi thu kstra Ví d : Tìm ư ng i ng n nh t t A G Shortest T ph pA AB=2,AC=4.AD=7,AF=5A,B AC=4.AD=7,AF=5,BE=3AB=2 ,BG=8,BD=6A,B,C AD=7,AF=5,BE=3,BG=8AB=2,AC=4 ,A,B,C,E AD=7,AF=5,BG=8AB=2,AC=4,BE=3A,B,C,E,F BG=8,FD=1AB=2,AC=4,BE=3A,B,C,E,F,D BG=8AB=2,AC=4,BE=3,FD=1 Gi i thu t D kstra Gi thu kstra- Hình bên là cây ư ng i ng n nh t t nh A n các nh- V i ví d : A G, gi i thu t s k t thúc n u tìm th y nh G Gi i thu t D kstra Gi thu kstraTìm cây ư ng i ng n nh t t nh C n các nhcòn l i c a th sau: Gi i thu t D kstra Gi thu kstra ph c t p c a thu t toán:- Bình thư ng thu t toán Dijkstra có ph c t p O(n2+m).- N u s d ng c u trúc heap O((n+m)*log2(n)) Gi i thu t Floyd-Warshall Gi thu FloydBài toán: Tìm ư ng i ng n nh t c a m i c p nhtrong th (All-Pairs Source Shortest Path)