ilyakrasnovv's blog

By ilyakrasnovv, 2 months ago, translation, In English

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);
            }
        }
    }
}
We remember...
 
 
 
 
  • Vote: I like it
  • +82
  • Vote: I do not like it

»
2 months ago, # |
Rev. 3   Vote: I like it +8 Vote: I do not like it

This appears to be a specific case of Dial's algorithm, and in general, you can extend this to edge weights up of size $$$k$$$ in $$$\mathcal O(nk + m)$$$ with $$$k + 1$$$ queues as described here.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Also, I'm a little confused on how the $$$A-2A$$$ problem is equivalent to $$$1-2$$$. Is the problem that you have edge weights of length $$$A, A + 1, A + 2, \dots, 2A - 1$$$? Then you say in order to avoid fractional weights, we multiply by some constant first to make them divisible by $$$A$$$, which presumably has to be $$$A$$$ in most cases, so dividing by $$$A$$$ just gives us back our original weights again, so you still have $$$2nA$$$ and not just $$$2n$$$ unique distances?

    • »
      »
      »
      2 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      The main point of both algorithms is that you can have fractional weight, and that really fractional weights aren't a big problem for 1-k bfs. (But no for 0-k!)

      You can have fractional weights and not only $$$A, A + 1, A + 2, ..., 2A - 1$$$, you can also have weights such as $$$A + 0.5$$$ if it is less than $$$2A$$$, as well as A can be equal to $$$1.333$$$ or $$$10^{18}$$$.

      I multiply them by some number not to make them divisible by A, but to get rid of fractional weights (because we don't want to have such problems as famous $$$0.1 + 0.2$$$). In most cases, I think, multiplying by $$$10^9$$$ will work. During translations I forgot to mention, that we should also multiply $$$A$$$ by this constant.

      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Ah, I think I misunderstood what the algorithm was trying to achieve. So to clarify:

        We have fractional weights in the range $$$[1, 2)$$$ (i.e. $$$1.2$$$ and $$$1.555$$$ are permitted). Whenever we transition from a node with shortest distance of, say $$$2.4$$$, then $$$\text{floor}(2.4 + \text{edge weight}) > 2$$$, and in general $$$\text{floor}(\text{old dist} + \text{edge weight}) > \text{floor}(\text{old dist})$$$, putting it in the next queue. And that's why we can use only indices $$$0, 1, 2, \dots, 2(n - 1)$$$, instead of $$$\mathcal O(n \cdot \text{precision})$$$ indices. And that's also why edge weights need to be $$$\geq 1$$$.

        • »
          »
          »
          »
          »
          2 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Yeah, but not always in the next queue, sometimes to queues further. And yes, as you have told, the cool part is that you can store only $$$\mathcal{O}(n)$$$ queues.