# 0-1 BFS

[TOC]

## Giới thiệu

Bài toán tìm đường đi ngắn nhất trên đồ thị là một bài toán cổ điển, có tính ứng dụng thực tế cao và hay xuất hiện ở các cuộc thi lập trình thi đấu.

Thông thường, để tìm đường đi ngắn nhất từ một đỉnh đến tất cả các đỉnh khác trong một đồ thị (thưa), ta có thể áp dụng thuật toán [Dijkstra](https://vnoi.info/wiki/algo/graph-theory/shortest-path.md).

Tuy nhiên, trong trường hợp trọng số của cạnh chỉ là 0 hoặc 1, chúng ta có thể áp dụng một thuật toán tối ưu hơn:

## Thuật toán 0-1 BFS

Trước hết chúng ta có thể phân tích thuật toán Dijkstra trong trường hợp cạnh trọng số 0-1.

Đây là cài đặt mẫu của thuật toán Dijkstra:

vector<int> d(n, INF);
d[s] = 0;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>> q;
q.push({0, s});
while (!q.empty()) {
    int u = q.top().first;
    int dd = q.top().second;
    q.pop();
    
    if (dd > d[u]) continue;
    for (auto edge : adj[u]) {
        int v = edge.first;
        int w = edge.second;

        if (d[u] + w < d[v]) {
            d[v] = d[u] + w;
            q.push({d[v], v});
        }
    }
}

Ta có thể thấy rằng khoảng cách từ gốc của 2 đỉnh bất kỳ trong hàng đợi cách nhau không quá 1 đơn vị, nghĩa là `d[u] = d[v]` hoặc `d[u] = d[v] + 1`. Điều này là do thuật toán Dijkstra luôn xét từ đỉnh gần gốc nhất và mỗi lần chỉ thêm vào hàng đợi đỉnh có khoảng cách bằng hoặc lớn hơn 1 đơn vị.

Như vậy, cấu trúc của hàng đợi sẽ như sau:

$$Q = \underbrace{u}_{d[u]}, \dots, \underbrace{v'}_{d[u]}, \underbrace{v''}_{d[u]+1} \dots \underbrace{v'''}_{d[u]+1}$$

Với cấu trúc đơn giản như vậy, ta có thể dùng một hàng đợi 2 đầu (deque) thay vì một hàng đợi ưu tiên.

Khi xét đến cạnh có trọng số 0, `d[v] = d[u]` và ta sẽ thêm vào đầu hàng đợi.

Khi xét đến cạnh có trọng số 1, `d[v] = d[u] + 1` và ta sẽ thêm vào cuối hàng đợi.

## Cài đặt mẫu

vector<int> d(n, INF);
d[s] = 0;
deque<int> q;
q.push_front(s);
while (!q.empty()) {
    int u = q.front();
    q.pop_front();
    for (auto edge : adj[u]) {
        int u = edge.first;
        int w = edge.second;
        if (d[u] + w < d[v]) {
            d[v] = d[u] + w;
            if (w == 1) {
                q.push_back(v);
            } else {
                q.push_front(v);
            }
        }
    }
}

## Đánh giá

Độ phức tạp của thuật toán là $\mathcal{O}(|V|+|E|)$, bằng độ phức tạp của BFS, và nhanh hơn nhiều so với thuật toán Dijkstra với độ phức tạp là $\mathcal{O}(|E|\log|V|)$ hoặc $\mathcal{O}(|V|^2+|E|)$.

## Mở rộng

Thuật toán này có thể mở rộng ra với cạnh có trọng số $\leq K$ với tên gọi là "thuật toán của Dial" với độ phức tạp $\mathcal{O}(|V| \cdot K+|E|)$. Các bạn có thể đọc thêm ở [đây](https://codeforces.com/blog/entry/88408).

## Bài tập

- [SPOJ: KATHTHI](https://www.spoj.com/problems/KATHTHI/)
- [Codeforces: 590C](https://codeforces.com/problemset/problem/590/C)