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.
Breath First Search (BFS) cùng với Depth First Search là những thuật toán cơ bản dùng để duyệt qua đồ thị. Trong bài viết này, chúng ta sẽ cùng làm rõ ý tưởng cũng như cách hiện thực thuật toán này.
