0–1 BFS: tìm đường ngắn nhất bằng deque

Vì sao BFS thường chưa đủ?

BFS thông thường ưu tiên đường có ít cạnh nhất. Nếu một cạnh đi thẳng tốn 1 còn hai cạnh đi vòng đều tốn 0, đường hai cạnh mới có chi phí thấp hơn. Mục tiêu đã đổi từ đếm bước sang cộng trọng số, nên cách đánh dấu lần đầu của BFS không còn dùng nguyên xi được.

Xét cạnh 0 → 1 trọng số 1, 0 → 2 trọng số 0 và 2 → 1 trọng số 0. Nếu đánh dấu đỉnh 1 ngay khi thấy cạnh trực tiếp, ta giữ d[1]=1 và bỏ đường qua 2. Đáp án thật là 0. Đây là phản ví dụ nhỏ để kiểm bất kỳ cách cài nào đang trộn BFS thường với trọng số.

Bạn có thể dùng Dijkstra vì trọng số vẫn không âm. Tuy nhiên, khi trọng số chỉ thuộc hai giá trị 0 và 1, việc chọn gần nhất có thể thực hiện bằng deque, không cần heap tổng quát. Đây là lý do 0–1 BFS là một trường hợp đặc biệt hữu ích của bài đường ngắn nhất.

Deque giữ thứ tự khoảng cách ra sao?

Giả sử trạng thái hợp lệ đầu deque có khoảng cách D. Từ nó, cạnh 0 chỉ tạo ứng viên D, còn cạnh 1 tạo ứng viên D+1. Các trạng thái cùng khoảng cách D cần xử lý trước lớp D+1, nên đặt ứng viên 0 ở đầu và ứng viên 1 ở cuối.

Điều đáng chú ý là deque này không hoạt động như stack thuần hoặc queue thuần. Nó ưu tiên theo hai lớp chi phí đang kề nhau. Khi hết lớp D, lớp D+1 lên đầu và quá trình tiếp tục. Tính chất này phụ thuộc trực tiếp vào miền trọng số, không phải chỉ do ta dùng một cấu trúc có hai đầu.

Đừng suy rộng bằng cách thấy trọng số 2 thì thêm cuối hai lần. Nhân số bản ghi không mô phỏng đúng khoảng cách và còn tạo dữ liệu thừa. Với trọng số tổng quát, dùng Dijkstra hoặc một thuật toán phù hợp với miền trọng số đã chứng minh được.

Chạy tay: một đỉnh được cải thiện hai lần

Tệp ví dụ lưu các cạnh từ 0 theo thứ tự tới 1 rồi tới 2. Mỗi mục trong deque là cặp (khoảng cách lúc thêm, đỉnh), không phải chỉ nhãn đỉnh. Ban đầu chỉ có (0,0).

Dãy cuối là [0,0,0,0,1]. Trạng thái (1,1) vẫn nằm trong deque sau khi d[1] đã giảm về 0. Code so khoảng cách lấy ra với mảng d rồi bỏ bản ghi cũ, tránh quét lại cạnh bằng thông tin hết hiệu lực.

Nới lỏng thay vì visited lần đầu

Với u → v trọng số w, thử nd=d[u]+w. Nếu v chưa tới được hoặc nd nhỏ hơn d[v], cập nhật và đưa bản ghi mới vào đầu hoặc cuối phù hợp. Nếu chỉ bằng nhau, không đưa thêm. Điều kiện giảm nghiêm ngặt giúp chu trình 0 không làm hàng chờ sinh vô hạn.

Khác với BFS không trọng số, trạng thái chưa được lấy ra có thể bị cải thiện như đỉnh 1 trong bảng. Vì vậy, một cờ visited gán ngay lần thêm đầu tiên sẽ chặn đường tốt hơn. Nếu bạn chọn thiết kế chốt khi lấy ra thì phải giữ đúng chứng minh thứ tự khoảng cách; code của bài dùng cách kiểm trạng thái cũ để thể hiện rõ sự khác nhau này.

Đỉnh không đi tới được giữ −1. Do mọi khoảng cách hợp lệ đều không âm, −1 là ký hiệu an toàn cho ví dụ. Khi dùng một số INF thay thế, hãy vẫn phân biệt trạng thái chưa tới được với một chi phí hữu hạn.

Code C++ và Python

#include <deque>
#include <iostream>
#include <utility>
#include <vector>
using namespace std;
vector<int> shortest(const vector<vector<pair<int,int>>>& g,int s){
    vector<int> d(g.size(),-1);
    deque<pair<int,int>> q;
    d[s]=0;q.push_back({0,s});
    while(!q.empty()){
        auto [du,u]=q.front();q.pop_front();
        if(du!=d[u])continue;
        for(auto [v,w]:g[u]){
            int nd=du+w;
            if(d[v]!=-1 && d[v]<=nd)continue;
            d[v]=nd;
            if(w==0)q.push_front({nd,v});
            else q.push_back({nd,v});
        }
    }
    return d;
}
int main(){
    int n=5,m=5,s=0;
    vector<vector<pair<int,int>>> g={{{1,1},{2,0}},{{3,0}},{{1,0}},{{4,1}},{}};
    if(cin>>n>>m>>s){
        g.assign(n,{});
        for(int i=0,u,v,w;i<m;++i){cin>>u>>v>>w;g[u].push_back({v,w});}
    }
    for(int x:shortest(g,s))cout<<x<<' ';
    cout<<'\n';
}

from collections import deque
import sys

def shortest(g,s):
    d=[-1]*len(g)
    d[s]=0
    q=deque([(0,s)])
    while q:
        du,u=q.popleft()
        if du!=d[u]:
            continue
        for v,w in g[u]:
            nd=du+w
            if d[v]!=-1 and d[v]<=nd:
                continue
            d[v]=nd
            if w==0:
                q.appendleft((nd,v))
            else:
                q.append((nd,v))
    return d

if __name__=='__main__':
    a=list(map(int,sys.stdin.buffer.read().split()))
    g=[[(1,1),(2,0)],[(3,0)],[(1,0)],[(4,1)],[]]
    s=0
    if a:
        n,m,s=a[:3]
        g=[[] for _ in range(n)]
        for i in range(m):
            u,v,w=a[3+3*i:6+3*i]
            g[u].append((v,w))
    print(*shortest(g,s))

Không nhập dữ liệu thì chương trình chạy hình minh họa và in 0 0 0 0 1. Dữ liệu riêng bắt đầu bằng n, m, s, tiếp theo m bộ u v w. Đỉnh từ 0 tới n−1, n dương, s hợp lệ; w phải là 0 hoặc 1. Đây là đồ thị có hướng, có thể có cạnh song song và cạnh tự nối.

Python dùng collections.deque với appendleft, append và popleft. Không dùng list.insert(0,...) cho thao tác đầu vì phải dịch các phần tử phía sau. C++ dùng deque<pair<int,int>>, giữ cả chi phí của bản ghi để so với d[u] lúc lấy ra.

Nếu dữ liệu cho đường hai chiều, thêm cả hai chiều khi dựng danh sách kề. Nếu đề hỏi một đích, chỉ có thể dừng khi lấy ra trạng thái hiện hành của đích theo thứ tự ưu tiên; dừng ngay lần phát hiện vẫn mắc phản ví dụ d[1] bên trên.

Mô hình hóa chi phí 0 và 1

Một kiểu bài thường gặp là giữ nguyên lựa chọn hiện tại thì chi phí 0, thay lựa chọn thì chi phí 1. Chẳng hạn từ một ô, đi theo hướng được chỉ sẵn là miễn phí, rẽ sang hướng khác tính một lần thay đổi. Mỗi ô là một đỉnh, mỗi cách chuyển là một cạnh mang đúng chi phí của hành động đó.

Nhưng cần đọc kỹ chi phí được thu mỗi lần đi, mỗi ô thay đổi hay chỉ một lần cho toàn bộ cấu hình. Mô hình cạnh 0/1 chỉ giải được khi trạng thái chứa đủ thông tin để biết chi phí bước tiếp theo. Nếu một thay đổi ảnh hưởng lâu dài tới tương lai, chỉ lưu vị trí hiện tại có thể thiếu trạng thái và làm đáp án sai dù thuật toán đường đi đã cài đúng.

Một ví dụ khác là đảo chiều một số cạnh: đi theo chiều gốc tốn 0, đi chiều ngược tốn 1. Từ mỗi cạnh có hướng u → v, thêm cạnh giá 0 từ u tới v và cạnh giá 1 từ v về u. Kết quả khi đó là số lần dùng chiều ngược trên đường đi trong mô hình này, không tự động là số cạnh phải sửa cho mọi cặp đỉnh của toàn mạng.

Cận thời gian và bộ nhớ

Nhờ thứ tự hai lớp, khi một trạng thái hiện hành được mở rộng, nó có khoảng cách tối ưu; các bản ghi cũ bị bỏ qua. Mỗi danh sách cạnh của đỉnh được quét khi xử lý trạng thái hợp lệ, và mỗi cập nhật gắn với một lần xét cạnh. Tổng thời gian O(n+m); lưu đồ thị, mảng khoảng cách cùng bản ghi chờ có cận O(n+m).

Đây là phân tích thao tác, không phải hứa số giây cụ thể. Với Python, đọc input và biểu diễn danh sách cặp cũng có chi phí bộ nhớ đáng kể. Nếu n,m rất lớn, cần xét giới hạn bộ nhớ của cả chương trình chứ không chỉ mảng d.

Ba ca tự luyện để nhận đúng lỗi

Một: dùng ba đỉnh với các cạnh 0 → 1 giá 1, 0 → 2 giá 0, 2 → 1 giá 0. d[1] phải bằng 0. Hai: thêm chu trình 1 → 2 và 2 → 1 đều giá 0; chương trình vẫn phải dừng. Ba: thêm đỉnh cô lập; kết quả của nó phải là −1, không phải 0.

Khi tự kiểm tra trên đồ thị nhỏ có cạnh song song trọng số 0 và 1, bạn có thể đối chiếu mảng khoảng cách của 0-1 BFS với kết quả chạy Dijkstra chuẩn. Hãy so sánh giá trị khoảng cách ngắn nhất tới từng đỉnh thay vì bắt buộc thứ tự lấy đỉnh ra khỏi deque phải cố định.

Luyện ngay trên Big-O Coding

Bài dưới luyện đúng đồ thị trọng số 0/1. Trước khi viết code, tự chạy phản ví dụ ba đỉnh rồi kiểm cách chọn đầu hoặc cuối của deque. Sau khi giải xong, thử cài lại bằng Dijkstra để đối chiếu khoảng cách trên các dữ liệu nhỏ.

Câu hỏi thường gặp

Nguồn tham khảo

• CP-Algorithms: 0–1 BFS
• Python: collections.deque
• C++ reference: deque