Thuật toán Dijkstra là gì? Giải thích dễ hiểu kèm demo trực quan

Bài viết này giúp làm rõ ý tưởng của Dijkstra, cách hoạt động và kèm theo một demo trực quan bằng JavaScript để quan sát từng bước thuật toán chạy.

Dijkstra giải bài toán gì?

Bài toán cơ bản của Dijkstra là:

• Cho một đồ thị có trọng số không âm.
• Chọn một đỉnh nguồn bắt đầu.
• Tìm khoảng cách ngắn nhất từ đỉnh nguồn đến các đỉnh còn lại.

Trong nhiều trường hợp thực tế, ta chỉ quan tâm đến đường đi ngắn nhất giữa hai đỉnh, nhưng Dijkstra thực chất tính được khoảng cách từ nguồn đến mọi đỉnh có thể tới được.

Mô hình hóa đồ thị có trọng số

Để minh họa, sử dụng một đồ thị nhỏ với các đỉnh từ A đến F và các cạnh có trọng số như sau:

A → B (2), C (4)
B → D (1), E (7)
C → E (3), F (5)
D → F (4)
E → F (1)

Trong demo, đồ thị được xem như vô hướng, nghĩa là nếu có A → B thì có thể đi từ B → A với cùng trọng số.

Ý tưởng chính của thuật toán Dijkstra

Dijkstra sử dụng cách tiếp cận tham lam (greedy) với các bước chính:

1. Gán khoảng cách ban đầu từ nguồn đến chính nó là 0, đến các đỉnh khác là vô cùng.
2. Chọn đỉnh chưa xử lý có khoảng cách tạm thời nhỏ nhất.
3. Cố định khoảng cách đến đỉnh đó (coi như đã tối ưu).
4. Dùng đỉnh vừa chọn để cập nhật (relax) khoảng cách đến các đỉnh kề.
5. Lặp lại cho đến khi không còn đỉnh nào có thể cải thiện khoảng cách.

Nhờ cách chọn đỉnh có khoảng cách nhỏ nhất ở mỗi bước, Dijkstra đảm bảo khoảng cách khi “chốt” một đỉnh là khoảng cách ngắn nhất từ nguồn đến đỉnh đó.

Demo Dijkstra bằng JavaScript

Demo dưới đây cho phép chọn đỉnh bắt đầu và đỉnh kết thúc, sau đó chạy Dijkstra để:

• Hiển thị bảng khoảng cách tạm thời từ nguồn đến từng đỉnh.
• Minh họa các bước thuật toán: chọn đỉnh hiện tại, cập nhật khoảng cách.
• Hiển thị đường đi ngắn nhất và tổng trọng số.

Phân tích đoạn code Dijkstra

1. Khởi tạo dữ liệu

Đầu tiên, thuật toán gán khoảng cách của mọi đỉnh là vô cùng, ngoại trừ đỉnh bắt đầu:

nodes.forEach(function(n) {
    distances[n] = Infinity;
    previous[n] = null;
    visited[n] = false;
});
distances[start] = 0;

Mảng distances lưu khoảng cách tạm thời, previous lưu đỉnh trước đó trên đường đi, còn visited đánh dấu đỉnh đã được cố định khoảng cách.

2. Chọn đỉnh có khoảng cách nhỏ nhất chưa xử lý

var current = null;
var minDist = Infinity;

nodes.forEach(function(n) {
    if (!visited[n] && distances[n] < minDist) {
        minDist = distances[n];
        current = n;
    }
});

Mỗi vòng lặp, thuật toán chọn đỉnh có khoảng cách tạm thời nhỏ nhất và chưa được đánh dấu là đã xử lý. Đỉnh này được xem là “đỉnh hiện tại”.

3. Cập nhật (relax) các đỉnh kề

graph[current].forEach(function(edge) {
    var neighbor = edge.to;
    if (visited[neighbor]) return;

    var alt = distances[current] + edge.w;
    if (alt < distances[neighbor]) {
        distances[neighbor] = alt;
        previous[neighbor] = current;
    }
});

Nếu đi đến đỉnh kề thông qua đỉnh hiện tại giúp giảm tổng trọng số, thuật toán cập nhật lại khoảng cách và ghi nhận đỉnh trước đó.

Khi nào nên dùng Dijkstra?

• Khi đồ thị có trọng số và tất cả trọng số đều không âm.
• Khi cần tìm đường đi ngắn nhất từ một đỉnh nguồn đến các đỉnh khác.
• Khi tối ưu quãng đường, thời gian hoặc chi phí trong các bài toán đường đi.
• Khi cần thuật toán ổn định, dễ hiểu và có thể mở rộng sang dạng dùng hàng đợi ưu tiên (priority queue) cho đồ thị lớn.

Kết luận

Dijkstra là thuật toán cốt lõi cho rất nhiều bài toán tìm đường trong lập trình. Bằng cách luôn chọn đỉnh có khoảng cách tạm thời nhỏ nhất và dần dần cố định khoảng cách, thuật toán đảm bảo tìm được đường đi ngắn nhất trên đồ thị có trọng số không âm.

Với demo bằng JavaScript, từng bước chọn đỉnh, cập nhật khoảng cách và xây dựng đường đi cuối cùng đều được minh họa rõ ràng, giúp quá trình học và ghi nhớ Dijkstra trở nên trực quan hơn.

Từ nền tảng này, có thể tiếp tục tìm hiểu các biến thể nâng cao như dùng hàng đợi ưu tiên để tăng hiệu suất, hay kết hợp với heuristic để xây dựng thuật toán A* cho các bài toán tìm đường phức tạp hơn.