0-1 BFS (Đường đi ngắn nhất trên đồ thị trọng số nhị phân) trong C

Cho đồ thị các đỉnh và cạnh, mỗi cạnh trọng số 0 hoặc 1. Cho đỉnh nguồn, tìm đường đi ngắn nhất từ nguồn đến các đỉnh khác. Ví dụ đồ thị như hình:

BFS thông thường tất cả cạnh cùng trọng số. Ở đây có 0 và 1. Mỗi bước kiểm tra điều kiện khoảng cách tối ưu. Sử dụng hàng đợi hai đầu (deque) lưu đỉnh. Kiểm tra trọng số cạnh: nếu 0 thì đẩy vào đầu, ngược lại đẩy vào cuối. Xem thuật toán để hiểu rõ.

Thuật toán

binaryBFS(src) -

bắt đầu
    định nghĩa mảng dist lưu khoảng cách từ nguồn đến đỉnh i vào dist[i]. Khởi tạo vô cực
    dist[src] := 0
    đưa src vào hàng đợi Q.
    v := phần tử đầu Q, xóa khỏi hàng đợi
    trong khi Q không rỗng, làm
        với mỗi cạnh e nối với v, làm
            nếu trọng số v đến next của i > dist[v] + trọng số v đến i, thì cập nhật trọng số
                nếu trọng số là 0, đưa vào đầu, ngược lại đưa vào cuối
            kết thúc nếu
        xong
    xong
    in tất cả khoảng cách từ mảng dist
kết thúc

Ví dụ

#include <iostream>
#include <vector>
#include <deque>
#define V 8
using namespace std;

struct node {
    int next, weight;
};

vector <node> edges[V];

void binaryBFS(int src) {
    int dist[V];
    for (int i=0; i<V; i++) // khởi tạo vô cực
        dist[i] = INT_MAX;
    deque <int> Q;
    dist[src] = 0; // khoảng cách từ nguồn đến nguồn là 0
    Q.push_back(src);
    while (!Q.empty()) {
        int v = Q.front(); // lấy đỉnh đầu, xóa khỏi hàng đợi
        Q.pop_front();
        for (int i=0; i<edges[v].size(); i++) {
            // kiểm tra khoảng cách tối ưu
            if (dist[edges[v][i].next] > dist[v] + edges[v][i].weight) {
                dist[edges[v][i].next] = dist[v] + edges[v][i].weight;
                if (edges[v][i].weight == 0) // cạnh trọng số 0 đưa vào đầu, ngược lại cuối
                    Q.push_front(edges[v][i].next);
                else
                    Q.push_back(edges[v][i].next);
            }
        }
    }
    for (int i=0; i<V; i++)
        cout << dist[i] << " ";
}

void addEdge(int u, int v, int wt) {
    edges[u].push_back({v, wt});
    edges[v].push_back({u, wt});
}

int main() {
    addEdge(0, 1, 0);
    addEdge(0, 3, 1);
    addEdge(0, 4, 0);
    addEdge(1, 2, 1);
    addEdge(1, 7, 0);
    addEdge(2, 5, 1);
    addEdge(2, 7, 0);
    addEdge(3, 4, 0);
    addEdge(3, 6, 1);
    addEdge(4, 6, 1);
    addEdge(5, 7, 1);
    addEdge(6, 7, 1);
    int src = 6;
    binaryBFS(src);
}

Kết quả

1 1 1 1 1 2 0 1