Thuật toán Dijkstra: Tìm đường đi ngắn nhất

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ố. Ý tưởng cơ bản của thuật toán Dijkstra là từ điểm gốc, tìm đường đi ngắn nhất đến các điểm khác trong đồ thị.

Thuật toán Dijkstra và cách hoạt động

Thuật toán Dijkstra có thể giải quyết bài toán tìm đường đi ngắn nhất trên đồ thị vô hướng và có hướng, miễn là trọng số không âm. Ý tưởng cơ bản của thuật toán như sau:

Bạn đang xem: Thuật toán Dijkstra: Tìm đường đi ngắn nhất

Bước 1: Khởi tạo khoảng cách

• Từ đỉnh gốc, khởi tạo khoảng cách tới chính nó là 0, và khoảng cách tới các đỉnh khác là vô cùng.
• Ghi nhận danh sách khoảng cách tới các đỉnh.

Bước 2: Chọn đỉnh và ghi nhận

• Chọn đỉnh a có khoảng cách nhỏ nhất trong danh sách và ghi nhận.
• Loại bỏ đỉnh a khỏi danh sách.

Bước 3: Cập nhật khoảng cách

• Xét các đỉnh kề b của đỉnh a.
• Nếu khoảng cách từ đỉnh gốc tới đỉnh b nhỏ hơn khoảng cách hiện tại đã ghi nhận, cập nhật giá trị và đỉnh kề a vào khoảng cách của b.

Bước 4: Lặp lại quá trình

• Sau khi xét tất cả các đỉnh kề b của đỉnh a, ta được danh sách khoảng cách đã cập nhật.
• Quay lại bước 2 với danh sách mới.
• Thuật toán kết thúc khi tìm được khoảng cách nhỏ nhất từ đỉnh gốc tới tất cả các đỉnh.

Để dễ hiểu hơn về ý tưởng của thuật toán Dijkstra, chúng ta xem xét ví dụ với đồ thị vô hướng G. Thuật toán sẽ tìm khoảng cách từ đỉnh gốc 0 tới tất cả các đỉnh còn lại trong đồ thị G.

Bước đầu tiên, ta khởi tạo khoảng cách từ đỉnh gốc 0 tới các đỉnh khác là vô cùng và khoảng cách tới đỉnh gốc là 0.

Tiếp theo, chọn đỉnh 0 có khoảng cách nhỏ nhất và xét các đỉnh kề của đỉnh 0.

Xem thêm : Tra Cứu Mệnh Ngũ Hành

Sau khi xét tất cả các đỉnh, ta chọn đỉnh 2 có khoảng cách nhỏ nhất và tiếp tục quá trình.

Cuối cùng, thuật toán kết thúc khi đã tìm được khoảng cách nhỏ nhất từ đỉnh gốc tới tất cả các đỉnh.

Tổng kết

Thuật toán Dijkstra là một thuật toán quan trọng và cổ điển để tìm đường đi ngắn nhất trong đồ thị. Với ý tưởng cơ bản đơn giản, thuật toán Dijkstra có thể giải quyết hiệu quả bài toán này trên các đồ thị có trọng số không âm. Hi vọng bài viết đã giúp bạn hiểu rõ hơn về thuật toán Dijkstra và cách hoạt động của nó.

Tham khảo

• Dijkstra’s algorithm

Nguồn: https://ispacedanang.edu.vn
Danh mục: Học tập