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

Các thuật toán tìm đường đi ngắn nhất luôn có sự chú ý rất cuồng nhiệt, bởi ứng dụng của nó là cực lớn, trong tài liệu này các bạn sẽ được làm quen với thuật toán dijkstra nổi tiếng.
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 19) Thu t toán Dijkstra-Prim Thu to Ví d : MST Q L a,b,c,i,f h,d,g,e R ng 18 a,b,c,i,f,g h,d,e R ng 20 Thu t toán Dijkstra-Prim Thu to Ví d : MST Q L a,b,c,i,f,g h,d,e R ng 20 a,b,c,i,f,g,h d,e R ng 21 Thu t toán Dijkstra-Prim Thu to Ví d : MST Q L a,b,c,i,f,g,h d,e R ng 21 a,b,c,i,f,g,h,d e R ng 28 Thu t toán Dijkstra-Prim Thu to Ví d : MST Q L a,b,c,i,f,g,h,d e R ng 28 a,b,c,i,f,g,h,d,e R ng R ng 36 Thu t toán Dijkstra-Prim Thu to ánh giá gi i thu t: - ph c t p c a gi i thu t Prim ph thu c vào cách th c hi n ưu tiên hàng i Q - N u Q ư c th c hi n như m t heap nh phân thì th i gian tính toán c a gi i thu t là O (E lgV) Thu t toán Kruskal Thu to Gi i thi u: - Khác v i gi i thu t Dijkstra-Prim b t u v i 1 nh b t kì ê xây d ng MST. Thu t toán Kruskal t p trung vào các c nh c a th Gi i thu t: - B t u v i MST r ng - Thêm vào MST các c nh có th t tăng d n theo tr ng s cho n khi t t c các nh ư c k t n i Thu t toán Kruskal Thu to Ví d : MST V R ng A,B,C,D,E,F,G FD A,B,C,E,G FD,AB C,E,G FD,AB,BE C,G FD,AB,BE,AC G FD,AB,BE,AC,AF G FD,AB,BE,AC,AF,DG R ng Thu t toán Kruskal Thu to ph c t p c a gi i thu t: - Thu t toán Kruskal có ph c t p là O(E lgE) Bài t p: S d ng thu t toán Dijkstra-Prim tìm MST c a th sau, b t u b t node C. Trình các bư c bày y Thu t toán Kruskal Thu to Bài t p: S d ng thu t toán Krusal tìm MST c a th sau.Trình bày y các bư c Ư NG I NG N NH T NG NH