Special case — 1-2-BFS

The task: we are given a weighted directed graph, where weight of every edge is in range $$$[1;2)$$$. We have to find shortest path from vertex $$$st$$$ to all the others.

Solution: for every integer in range from $$$0$$$ to $$$2n - 1$$$ we will store a queue of vertices (let the $$$i$$$-th queue be $$$q_i$$$). In $$$i$$$-th queue there will be all the vertexes, distance to which is $$$\lfloor i \rfloor$$$ (and some vertexes with smaller distance). To calculate this, we will do it layer-by-layer.

c++ realisation:

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 -- distance from st to all the others
                dist[e.first] = dist[v] + e.second;
                q[floor(dist[e.first])].push_back(e.first);
            }
        }
    }
}

Proof:

Base: $$$q_0$$$ ans $$$q_1$$$ are calculated correctly.

Assumption: for $$$x \ge 1$$$ all the layers $$$q_0, q_1, ..., q_x$$$ are calculated correctly, and distances to vertices in them are also calculated correctly.

Transition: then layer $$$q_{x + 1}$$$ will be calculated correctly, and distances to vertices in it are also calculated correctly:

Let's choose any vertex v, so $$$\lfloor dist_v \rfloor = x + 1$$$. It couldn't appear in previous layers, but it will be in layer $$$x + 1$$$, because previous vertex on the path from $$$st$$$ to $$$v$$$ must be in layers $$$x - 1$$$ or $$$x$$$. They are calculated correctly, thus during one of relaxations our vertex will appear in layer $$$x + 1$$$ with correct distance to $$$st$$$.

Asymptotic: $$$\mathcal{O}(n + m)$$$, where n — is number of vertices, and m — is number of edges.

Comment: it is obvious, that you can do the same optimisation as in 1-k bfs and store only 3 layers, but the code provided is easier to understand.

A-2A-BFS

The difference from previous task is that edges' weigths are in range $$$[A; 2A)$$$, where $$$A > 0$$$. But it is very easy to solve it using previous solution — we just have to divide all weights by A. Important notice is that errors may appear with calculations using doubles, so we should avoid them if it is possible. In that case we can multiply A and all weights by some number, so all of them are integers, and then simply add vertices to the layer dist[v] / A.

Code for case, where all the weights are integers:

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);
            }
        }
    }
}