Частный случай — 1-2-BFS

Постановка задачи: дан взвешенный ориентированный граф, где для любого ребра вес лежит в диапазоне $$$[1;2)$$$. Найти кратчайший путь от заданной вершины (st) до всех вершин.

Решение: заведем для каждого целого числа от $$$0$$$ до $$$2n - 1$$$ очередь вершин (Пусть $$$i$$$-ая очередь это $$$q_i$$$). В $$$i$$$-ой очереди будут лежать все вершины, расстояние до которых $$$\lfloor i \rfloor$$$ (и возможно какие-то вершины с меньшим расстоянием). Чтобы такие насчитать, будем пересчитывать по слоям.

код на c++:

for (int i = 0; i < 2 * n; ++i) {
    for (int v : q[i]) {
        for (pair<int, double> e : g[v]) {
            if (dist[e.first] > dist[v] + e.second) { // dist -- расстояния до вершин от стартовой
                dist[e.first] = dist[v] + e.second;
                q[floor(dist[e.first])].push_back(e.first);
            }
        }
    }
}

Доказательство корректности алгоритма:

База: $$$q_0$$$ и $$$q_1$$$ построены правильно.

Предположение: Для $$$x \ge 1$$$ слои $$$q_0, q_1, ..., q_x$$$ построены правильно, и расстояния до вершин в них посчитаны правильно.

Переход: тогда слой $$$q_{x + 1}$$$ тоже построен правильно, и расстояния до вершин в нем правильные:

Посмотрим на любую вершину v, для которой $$$\lfloor dist_v \rfloor = x + 1$$$. Она точно не могла лежать в предыдущих слоях по предположению, а в слое $$$x + 1$$$ она лежит, так как предыдущая в пути от стартовой до нее точно лежала в слое $$$x - 1$$$ или $$$x$$$. А так как расстояния до всех возможных предыдущих посчитаны правильно, то и до новой вершины среди одной из релаксаций будет посчитано правильное расстояние.

Асимптотика: $$$\mathcal{O}(n + m)$$$, где n — число вершин, а m — число ребер.

Комментарий: очевидно, что как и в случае 1-k bfs тут можно обойтись и 3 слоями, но приведенный выше способ лучше для понимания.

Сведение к A-2A-BFS

Отличие этой задачи в том, что в отличие от предыдущей веса ребер находятся в диапазоне $$$[A; 2A)$$$, где $$$A > 0$$$. Свести к предыдущей очень просто — надо всего лишь поделить все веса на A. Важным замечанием является то, что при вычислениях может возникнуть погрешность, и лучше избегать нецелых чисел, если возможно. То есть если задана предельная точность, то стоит домножить A и все веса на обратное число, а вершины добавлять в очередь с номером dist[v] / A.

Ниже реализация на c++ для случая, где все веса целые.

for (int i = 0; i < 2 * n; ++i) {
    for (int v : q[i]) {
        for (pair<int, int> e : g[v]) {
            if (dist[e.first] > dist[v] + e.second) {
                dist[e.first] = dist[v] + e.second;
                q[dist[e.first] / A].push_back(e.first);
            }
        }
    }
}