Tóm tắt: Xác định đúng những cạnh mang chi phí 0 hoặc 1 giúp ta tối ưu thuật toán tìm đường đi ngắn nhất về thời gian tuyến tính.

Xét một đồ thị có các cạnh chỉ mang trọng số \(0\) hoặc \(1\), ví dụ như thao tác giữ nguyên trạng thái (chi phí \(0\)) hoặc thực hiện một lần đổi hướng (chi phí \(1\)). Giả sử ta đang xét đỉnh \(u\) có khoảng cách ngắn nhất hiện tại là \(d[u] = 2\). Từ \(u\), ta có một cạnh nối sang \(v\) với trọng số \(0\) và một cạnh sang \(w\) với trọng số \(1\). Khoảng cách mới tới \(v\) vẫn là \(2\), trong khi khoảng cách tới \(w\) tăng lên \(3\).

Dữ liệu nào cần được ghi nhớ? Nếu dùng hàng đợi ưu tiên priority_queue thông thường, ta phải tốn thêm chi phí \(O(\log V)\) cho mỗi lần cập nhật. Tuy nhiên, các giá trị khoảng cách được sinh ra từ \(u\) chỉ có thể là \(d[u]\) hoặc \(d[u] + 1\).

Nhận xét này dẫn trực tiếp tới kỹ thuật BFS 0-1 sử dụng deque (hàng đợi hai đầu). Ta luôn lấy đỉnh ở đầu hàng đợi để duyệt tiếp. Khi tối ưu được đỉnh \(v\) qua cạnh trọng số \(0\), ta đưa \(v\) vào đầu bằng push_front(v). Khi tối ưu đỉnh \(w\) qua cạnh trọng số \(1\), ta đưa \(w\) vào cuối bằng push_back(w).

Điều luôn đúng cần duy trì: khoảng cách của các đỉnh nằm trong deque luôn chênh lệch không quá \(1\) và không giảm từ đầu đến cuối. Danh sách thao tác cốt lõi gồm:

1. Xét cạnh \((u, v)\) trọng số \(0\): nếu \(d[v] > d[u]\), gán \(d[v] = d[u]\) và gọi push_front(v).
2. Xét cạnh \((u, w)\) trọng số \(1\): nếu \(d[w] > d[u] + 1\), gán \(d[w] = d[u] + 1\) và gọi push_back(w).

Mỗi khi tiếp cận một bài đồ thị có trọng số, bạn hãy thử phân tích xem mỗi bước chuyển trạng thái có thật sự cần một giá trị bất kỳ hay chỉ nhận hai mức chi phí \(0\) và \(1\). Nếu chỉ có hai mức, việc thay priority_queue bằng deque sẽ lập tức đưa độ phức tạp về \(O(V + E)\).