Thuật toán Dijkstra là một trong những thuật toán cổ điển để giải quyết bài toán tìm đường đi ngắn nhất từ một điểm cho trước tới tất cả các điểm còn lại trong đồ thị có trọng số. Trong bài viết này chúng ta cùng tìm hiểu ý tưởng cơ bản của thuật toán Dijkstra.
Ngoài thuật toán Prim, Thuật toán Kruskal cũng là thuật toán cổ điển để giải bài toán tìm cây khung nhỏ nhất (Minimum Spanning Tree) cho đồ thị vô hướng có trọng số. Trong bài viết này chúng ta cùng xem ý tưởng cơ bản của Thuật toán Kruskal.
Ở phần trước Thuật toán Prim: Cài đặt thuật toán chúng ta đã tìm hiểu qua cách cài đặt thuật toán Prim dựa vào Priority Queue. Tuy nhiên, có một nhược điểm là phải duyệt các cạnh không hợp lệ trong queue. Do vậy, trong bài này chúng ta sẽ tối ưu cách cài đặt thuật toán Prim ở bài trước bằng cách sử dụng Index Priority Queue.
Bài viết Thuật toán Prim: Tìm cây khung nhỏ nhất đã giới thiệu đến các bạn ý tưởng của thuật toán này cũng như từng bước chạy thuật toán. Tiếp theo sẽ là phần hướng dẫn cài đặt thuật toán Prim cho đồ thị vô hướng có trọng số bằng ngôn ngữ Java.
Hôm nay mình xin chia sẻ một số ghi chú về Thuật toán Prim dùng để giải bài toán tìm cây khung nhỏ nhất (Minimum Spanning Tree) cho đồ thị vô hướng có trọng số. Prim cũng là một trong những thuật toán cổ điển để giải bài toán này.
Bàn về độ phức tạp thời gian, mình vẫn thường hay nghe các bạn nói “Một vòng for là $O(N)$, hai vòng for lồng nhau là $O(N^2)$". Thực ra không hẳn là như thế, nó còn phụ thuộc vào số bước thực hiện mỗi lần lặp. Mình cũng sẽ không bàn về phương pháp khoa học để đánh giá thuật toán mà thay vào đó nói về cách để mường tượng xác định độ phức tạp của thuật toán.
