Bạn có bao giờ làm quen với bài toàn tìm một đường đi mà đường đó sẽ nối tới tất cả các đỉnh, và nó có độ dài nhỏ nhất. Trong phần này các bạn sẽ được làm quen với các thuật toán đóó | UNIVERSITY Minimum spanning tree Khái niệm x 1 J K J Á 1 Ả IK n r rri - Cây bao trùm tôi thiêu MST minimum spanning tree của một đô thị có trọng sô là một tập hợp các 1 1 Ấ. Ấ .A. 7 X 1 1 . Ấ 7 cạnh kêt nôi tât cả các đỉnh sao cho tông trọng sô của X 1 1 X 17 1 Ấ các cạnh là nhỏ nhât IK 1 1 V 1 Ấ 1 Ấ 1 X 1 1 Ấ V J 4- J1 - MST không nhât thiêt là duy nhât trong một đô thị 0 UNIVERSITY Minimum spanning tree Vi du HOA SEN UNIVERSITY Thuật toán Dijkstra-Prim Giới thiệu - Thuật toán do Edsger Dijkstra và . Prim tìm ra vào năm 1950 một cách độc lập - Giải thuật Prim dùng để giải bài toán cây bao trùm tối thiểu. - Giải thuật này sử dụng chiến lược để giải một bài toán tối ưu hóa giải thuật tham lam greedy Tại mỗi bước của giải thuật ta phải chọn một trong một số khả năng lựa chọn. Chiến lược tham lam đề xuất việc lựa chọn khả năng tốt nhất tại lúc .
