Đăng nhập để tham gia lộ trình luyện tập

Dijkstra — Từ nền tảng đến chuyên sâu

Dijkstra là một trong những thuật toán đường đi ngắn nhất quan trọng nhất trong Competitive Programming. Tuy nhiên, việc biết cài đặt một priority_queue và tính khoảng cách từ một đỉnh nguồn chưa đồng nghĩa với việc đã thực sự nắm vững Dijkstra.

Mục tiêu của lộ trình này là đưa người học đi từ khả năng cài đặt thuật toán cơ bản đến khả năng nhận diện và mô hình hóa những bài toán mà Dijkstra bị ẩn dưới các trạng thái, điều kiện, tài nguyên hoặc phép biến đổi khác nhau.

I. Mục tiêu

Sau khi hoàn thành toàn bộ lộ trình, người học cần đạt được các năng lực sau:

• hiểu chính xác bài toán Single-Source Shortest Path;
• hiểu điều kiện để Dijkstra hoạt động đúng;
• phân biệt BFS, 0-1 BFS, Dijkstra, Bellman-Ford và Floyd-Warshall;
• cài đặt Dijkstra bằng priority_queue một cách ổn định;
• phân tích đúng độ phức tạp của thuật toán;
• truy vết một đường đi ngắn nhất;
• xử lý nhiều đường đi ngắn nhất;
• đếm số đường đi ngắn nhất;
• tìm các cạnh hoặc đỉnh nằm trên đường đi ngắn nhất;
• xử lý nhiều nguồn bằng Multi-Source Dijkstra;
• sử dụng đồ thị đảo để giải các bài toán khoảng cách hai chiều;
• mô hình hóa grid thành đồ thị có trọng số;
• mô hình hóa trạng thái mở rộng (đỉnh, trạng thái);
• xây dựng Layered Graph;
• xử lý bài toán có coupon, vé miễn phí, số lần giảm giá hoặc tài nguyên hữu hạn;
• giải các bài toán shortest path trên đồ thị ẩn;
• xử lý nhiều khoảng cách tốt nhất đến cùng một đỉnh;
• hiểu ý tưởng K Shortest Paths;
• xây dựng Shortest-Path DAG;
• kết hợp Dijkstra với Dynamic Programming;
• nhận diện những bài toán không được phép dùng Dijkstra;
• chuyển một bài toán thực tế thành mô hình đường đi ngắn nhất thích hợp.

II. Kiến thức tiên quyết

Người học nên nắm được:

• mảng và vector;
• pair;
• priority_queue;
• danh sách kề;
• biểu diễn đồ thị có trọng số;
• BFS;
• DFS cơ bản;
• độ phức tạp Big-O;
• kiểu số nguyên 64-bit long long;
• khái niệm đường đi, trọng số và khoảng cách trên đồ thị.

III. Tư duy cốt lõi

Khi gặp một bài toán có khả năng sử dụng Dijkstra, không nên hỏi ngay:

“Có dùng Dijkstra được không?”

Thay vào đó hãy lần lượt xác định:

1. Trạng thái của bài toán là gì?
2. Một trạng thái có thể chuyển sang những trạng thái nào?
3. Mỗi phép chuyển có chi phí bao nhiêu?
4. Tổng chi phí của một lời giải có phải là tổng trọng số các phép chuyển hay không?
5. Các trọng số có không âm hay không?
6. Cần tìm khoảng cách nhỏ nhất từ đâu đến đâu?
7. Có cần lưu thêm thông tin ngoài đỉnh hiện tại hay không?

Nếu có thể biểu diễn bài toán dưới dạng:

trạng thái = đỉnh
hành động = cạnh
chi phí hành động = trọng số cạnh

thì bài toán có thể được xem như một bài toán đường đi ngắn nhất.

Điểm quan trọng nhất của Dijkstra nâng cao không nằm ở đoạn mã thuật toán, mà nằm ở việc xác định đúng không gian trạng thái.

IV. Nguyên tắc luyện tập

Lộ trình được tổ chức theo tiến trình:

Shortest Path cơ bản → Dijkstra chuẩn → Truy vết → Nhiều nguồn → Biến đổi đồ thị → Đồ thị trạng thái → Layered Graph → Dijkstra + DP → K Shortest Paths → Các mô hình tổng hợp nâng cao

Không nên bỏ qua các bài đầu ngay cả khi đã biết cài đặt Dijkstra.

Ở mỗi bài, cần tự trả lời được bốn câu hỏi:

1. Đỉnh của đồ thị là gì?
2. Cạnh của đồ thị là gì?
3. Trọng số của cạnh biểu diễn đại lượng nào?
4. Vì sao Dijkstra cho kết quả đúng?

V. Tiêu chuẩn hoàn thành

Một dạng bài chỉ được xem là đã nắm vững khi người học có thể:

• nhận diện dạng mà không nhìn tag;
• tự xây dựng mô hình đồ thị;
• giải thích trạng thái và phép chuyển;
• viết lại thuật toán từ đầu;
• phân tích đúng độ phức tạp;
• xử lý các trường hợp biên;
• giải được một biến thể chưa từng gặp nhưng có cùng cấu trúc.

Mục tiêu cuối cùng của lộ trình không phải là thuộc Dijkstra.

Mục tiêu là hình thành phản xạ:

Bài toán → Trạng thái → Đồ thị → Trọng số → Đường đi ngắn nhất → Thuật toán phù hợp.