Thuật toán Dijkstra

Cho một đồ thị có trọng số dương: G =(V,E), ký hiệu trọng số là w.
(1) a, z thuộc V. Tìm đường đi ngắn nhất từ a đến z.
(2) a thuộc V. Tìm (tất cả) các đường đi ngắn nhất từ a đến các đỉnh khác.
Input:
    G=(V, E)
    Đỉnh xuất phát a
    Đỉnh mục tiêu z

Output:
    1. Đường đi ngắn nhất từ a đến tất cả các đỉnh còn lại của đồ thị.

    2. Đường đi ngắn nhất từ a đến z.

Kết quả sẽ cho ta cây đường đi ngắn nhất xuất phát từ a.

💫💫💫

Mã giả

Tìm các đường đi ngắn nhất từ a đến các đỉnh còn lại (ở cùng thành phần liên thông với a).

Tìm đường đi ngắn nhất từ đỉnh a đến đỉnh z

 

Hướng dẫn giải tay