Thuật toán Dijkstra có ý tưởng đưa ra sẽ giúp người dùng dễ dàng tìm được đường đi ngắn nhất cho hoạt động công việc. Qua thuật toán sẽ giúp giải quyết bài toán tìm đường đi ngắn nhất trên đồ thị vô hướng lẫn có hướng miễn là trọng số không âm. Để hiểu rõ hơn về ý tưởng của thuật toán mời bạn đọc cùng FPT Aptech Hà Nội tham khảo, xem ngay nhé.

Thuật toán Dijkstra ý tưởng ra đời

Ý tưởng ra đời của thuật toán Dijkstra sẽ giúp giải quyết bài toán về tìm đường đi ngắn nhất trên đồ thị. Từ đó sẽ tìm được đường đi vô hướng lẫn có hướng miễn là trọng số không âm. Cụ thể các bước:

• Bước 1: Từ đỉnh gốc sẽ khởi tạo khoảng cách tới chính nó là 0. Khi đó sẽ khởi tạo khoảng cách nhỏ nhất ban đầu tới các đỉnh khác là +∞. Từ đó sẽ tìm được danh sách các khoảng cách tới các đỉnh cần tìm.

• Bước 2: Tiếp theo chọn đỉnh a có khoảng cách nhỏ nhất trong danh sách này và ghi nhận, từ các lần sau sẽ không xét tới đỉnh này nữa.

• Bước 3: Lần lượt tiếp theo đó sẽ 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 đang ghi nhận thì sẽ tiến hành cập nhật giá trị. Đồng thời cập nhập giá trị đỉnh kề a vào khoảng cách hiện tại của b.

• Bước 4: Sau khi xét tất cả đỉnh kề b của đỉnh a ta sẽ được danh sách khoảng cách tới các điểm đã được cập nhật. Khi đó tiến hành quay lại bước 2 với danh sách này và thuật toán kết thúc khi chọn được khoảng cách nhỏ nhất từ tất cả các điểm.

Tổng hợp sơ lược thuật toán Dijkstra tìm đường đi ngắn nhất

Sử dụng thuật toán Dijkstra sẽ giúp giải quyết tìm bài toán đường đi ngắn nhất của một nguồn, miễn là đồ thị trọng số không âm. Từ ý tưởng ra đời thuật toán sẽ thấy được sự tối giản đường đi bằng cách xét các cạnh và so sánh 2 đường đi sẵn có với đường qua cả 3 đỉnh.

Thuật toán hoạt động theo nguyên lý duy trì 1 tập hợp các đỉnh, trong đó chúng đã được biết chắc đường đi ngắn nhất. Tiến hành qua từng bước thuật toán sẽ giúp chọn ra một đỉnh mà chắc chắn đã được tối ưu hóa cao nhất. Sau tất cả các bước thì mọi đỉnh sẽ được chọn và mọi đường đi tìm được đều sẽ là ngắn nhất.

Thuật toán Dijkstra sẽ thường được lưu dưới dạng danh sách kề và có các lưu ý quan trọng sau:

• D[u] is short the most from the point to point u.

• W[u,v] là một số quan trọng trên đường đi từ điểm u đến điểm v.

• P[u] is a array mark of the point u with all the value of the ban đầu đều là Sai.

• Độ phức tạp của thuật toán được đánh giá là O(N^2 + M)

Để có thể tìm lại đường đã đi ngắn nhất điểm S về u thì sẽ tiến hành truy vết điểm đầu u theo mảng Trace và quay ngược lại S.

vector dấu vết_đường dẫn(vector &dấu vết, int S, int u) {

    if (u != S && trace[u] == -1) return vector(0); // không có đường đi

    véc tơ đường dẫn;

    while (u != -1) { // truy ngược vết từ u về S

        path.push_back(u);

        u = dấu vết [u];

    }

    reverse(path.begin(), path.end()); // cần phải đảo ngược vì đường đi lúc này là từ u về S

    đường về;

}

Lời kết

Hy vọng với thông tin được chia sẻ chi tiết trên sẽ giúp bạn đọc biết rõ về ý tưởng tưởng tượng ra đời của thuật toán Dijkstra. Ý tưởng này kết hợp với giải bài toán sẽ giúp ích rất nhiều cho người dùng khi ứng dụng thuật toán này. Nếu còn điều gì chưa hiểu còn thắc mắc hoặc cần biết rõ hơn về thuật toán hữu ích này bạn hãy đến với FPT Aptech ngay nhé.Tại Aptech Hà Nội bạn không chỉ được học về chi tiết về thuật toán Dijkstra C++ và nhiều vấn đề quan quan hệ khác.