Thuật toán Dijkstra — Tìm đường đi ngắn nhất từng bước

Thuật toán Dijkstra tìm đường đi ngắn nhất từ một nút xuất phát trong đồ thị có trọng số, miễn là mọi trọng số cạnh đều không âm. Nếu bạn chỉ quan tâm đến một đích cụ thể, bạn có thể dừng ngay khi đích đó được chốt.

Ý tưởng cốt lõi là tham lam: luôn tiếp tục từ nút chưa chốt có khoảng cách đã biết nhỏ nhất. Cách này chỉ đúng khi mọi trọng số đều không âm.

Thuật Toán Dijkstra Giải Quyết Bài Toán Gì

Dùng thuật toán Dijkstra khi bạn có một đồ thị với chi phí trên các cạnh và muốn tìm tuyến đường rẻ nhất. Chi phí đó có thể biểu diễn quãng đường, thời gian di chuyển, năng lượng, hoặc một đại lượng khác mà bạn muốn tối thiểu hóa.

Thuật toán hoạt động trên cả đồ thị có hướng và vô hướng. Điều kiện quan trọng là rất rõ ràng: mọi trọng số cạnh phải lớn hơn hoặc bằng $0$.

Thuật Toán Hoạt Động Như Thế Nào

Mỗi nút lưu một khoảng cách tạm thời từ nút bắt đầu. Ban đầu, nút bắt đầu có khoảng cách $0$ còn mọi nút khác có khoảng cách $\infty$.

Sau đó lặp lại vòng sau:

1. Chọn nút chưa chốt có khoảng cách tạm thời nhỏ nhất.
2. Xét từng nút kề thông qua nút đó.
3. Nếu đường đi mới rẻ hơn, cập nhật khoảng cách của nút kề.
4. Đánh dấu nút hiện tại là đã chốt.

Bước 3 được gọi là relaxation. Một nút đã chốt là nút đã hoàn tất: khoảng cách ngắn nhất của nó là cuối cùng, miễn là đồ thị không có cạnh trọng số âm.

Thuật Toán Dijkstra Từng Bước

Đây là toàn bộ quy trình ở dạng ngắn gọn:

1. Chọn một nút bắt đầu.
2. Đặt khoảng cách của nó là $0$ và mọi khoảng cách khác là $\infty$.
3. Chọn nút chưa chốt có khoảng cách tạm thời nhỏ nhất.
4. Nới lỏng các cạnh đi ra từ nút đó.
5. Đánh dấu nút đó là đã chốt.
6. Lặp lại cho đến khi mọi nút có thể tới đều được chốt, hoặc dừng khi nút đích của bạn được chốt.

Nếu bạn cũng lưu nút trước đó đã tạo ra mỗi lần cập nhật, bạn có thể khôi phục đường đi thực tế chứ không chỉ khoảng cách cuối cùng.

Ví Dụ Tìm Đường Đi Ngắn Nhất

Giả sử đồ thị có các trọng số cạnh sau:

• $A \to B = 4$
• $A \to C = 1$
• $C \to B = 2$
• $B \to D = 1$
• $C \to D = 5$

Ta muốn tìm đường đi ngắn nhất từ $A$ đến $D$.

Bắt đầu với:

$$\text{dist}(A)=0,\quad \text{dist}(B)=\infty,\quad \text{dist}(C)=\infty,\quad \text{dist}(D)=\infty$$

Chốt $A$ trước và nới lỏng các cạnh của nó:

$$\text{dist}(B)=4,\quad \text{dist}(C)=1$$

Lúc này khoảng cách chưa chốt nhỏ nhất nằm ở $C$, nên chốt $C$ tiếp theo.

Đi qua $C$:

• Qua $C$, đường đi đến $B$ có chi phí $1+2=3$, tốt hơn $4$, nên cập nhật $\text{dist}(B)=3$.
• Qua $C$, đường đi đến $D$ có chi phí $1+5=6$, nên đặt $\text{dist}(D)=6$.

Bây giờ $B$ có khoảng cách chưa chốt nhỏ nhất, nên chốt $B$.

Đi qua $B$, đường đi đến $D$ có chi phí:

$$3+1=4$$

Giá trị này tốt hơn $6$, nên cập nhật $\text{dist}(D)$ từ $6$ thành $4$.

Bây giờ $D$ là nút chưa chốt nhỏ nhất. Chốt nó và dừng lại.

Đường đi ngắn nhất là:

$$A \to C \to B \to D$$

với tổng chi phí:

$$1+2+1=4$$

Ví dụ này cho thấy mẫu hình quan trọng: một tuyến đường ban đầu có vẻ kém hơn, $A \to B$, về sau lại tốt hơn khi đi qua $C$. Thuật toán Dijkstra cho phép điều đó miễn là $B$ vẫn chưa được chốt. Khi một nút đã được chốt, khoảng cách của nó sẽ không đổi nữa.

Vì Sao Trọng Số Không Âm Lại Quan Trọng

Giả sử nút chưa chốt rẻ nhất hiện tại có khoảng cách là $d$. Mọi đường đi mới đến nút đó được tìm thấy về sau đều phải đi từ một nút chưa chốt khác có khoảng cách tạm thời ít nhất là $d$, rồi cộng thêm một cạnh có trọng số ít nhất là $0$.

Vì thế, đường đi xuất hiện muộn hơn đó không thể tốt hơn $d$. Đó là lý do việc chốt khoảng cách tạm thời nhỏ nhất là an toàn khi mọi trọng số đều không âm.

Nếu tồn tại một cạnh âm, lập luận đó sẽ không còn đúng. Một đường đi hiện trông có vẻ đắt có thể trở nên rẻ hơn về sau, nghĩa là chốt nút quá sớm có thể cho ra đáp án sai.

Những Lỗi Thường Gặp Với Thuật Toán Dijkstra

Dùng nó khi có cạnh âm

Chỉ một cạnh âm cũng có thể phá vỡ logic tham lam. Nếu có khả năng xuất hiện trọng số âm, hãy dùng một phương pháp tìm đường đi ngắn nhất khác.

Nhầm "đã thấy" với "đã xong"

Một nút có thể đã có khoảng cách tạm thời nhưng vẫn chưa hoàn tất. Chỉ nút đã chốt mới có khoảng cách ngắn nhất cuối cùng.

Quên bảng nút trước đó

Khoảng cách cho bạn biết chi phí. Nếu bạn cũng muốn biết chính xác tuyến đường, hãy lưu nút nào là nút cuối cùng đã cải thiện mỗi khoảng cách.

Thuật Toán Dijkstra Được Dùng Ở Đâu

Thuật toán Dijkstra được dùng khi bài toán có thể được mô hình hóa thành việc di chuyển qua một đồ thị với chi phí không âm:

• Lập kế hoạch tuyến đường trên bản đồ
• Định tuyến mạng
• Chuyển động robot trên lưới có trọng số
• Tìm đường trong game khi chi phí di chuyển thay đổi

Đây cũng là một ví dụ kinh điển về thuật toán tham lam mà tính đúng đắn phụ thuộc vào một điều kiện rất cụ thể.

Hãy Thử Một Bài Tương Tự

Hãy vẽ một đồ thị có năm nút và các trọng số cạnh dương, rồi tự chạy thuật toán Dijkstra bằng tay với một bảng khoảng cách. Nếu muốn tiến thêm một bước, hãy thử phiên bản của riêng bạn trên một đồ thị mới và kiểm tra chính xác khi nào mỗi nút trở nên an toàn để chốt.