### Yukuk's blog

By Yukuk, 15 months ago, translation, # Introduction

I recently noticed, that there is no Codeforces blog with explanation of 1-K BFS algorithm. So, I decided to create this blog for those, who likes reading tutorials here (like me).

# Algorithm If you are familiar with BFS (if not, I recommend to do it before reading), look at the picture. 1-K BFS also finds the shortest path in the graph, like BFS, and the only difference is that we have several queues. Let's look at this problem: Given graph with N vertexes and M edges, there's one non-zero digit on every edge. Every path corresponds to number formed by digits on edges. For each vertex, except the first, find the minimum sum of digits by the numbers corresponding to the paths from the first to it. N <= 10^7, M <= 5 * 10^7.

Let's rephrase the statement: "For each vertex, except the first, find the shortest path from the first to it". But restrictions don't allow us to use Dijkstra. Despite this, you can notice a very low restriction for edge weights — they belong to the segment [1;9]. "1-K" in the name of the algorithm means that exactly (here, K = 9).

Firstly, let's define an array of X queues, where X is a magic value, about which I'll tell a bit later, and push the first vertex to the 0's queue. Moreover, let's define an array d[v] — the answer for v (d[start] = 0) and an array used[v] — was v already used or not. So, if we're currently looking at vertex u and know the correct answer for it, we need to push each vertex w that u is connected to, to the (d[u] + "edge weight")'s queue. Because weights are positive, d[u] will never become better. We need to keep the position of queue, which we're currently analyzing, for example, in variable pos. We will increase it to the index of first non-empty queue in the beginning of every iteration.

It may seem, that X is pretty big, because answer can be equal to (N — 1) * K for some vertexes. But the magic is, that X can be equal K + 1. Why can we do that? At every moment, we need only K + 1 queues, because we cannot push vertexes to queues, which index is larger pos by more than K. So, just write % (K + 1) in [] and algorithm is ready!

Code for better understanding:

        bfs.push(start);
d[start] = 0;
int pos = 0, num = 1; // I recommend to define a variable num - the number of vertexes that are in the queues
while (num > 0)
{
while (bfs[pos % (k + 1)].empty())
{
++pos;
}
int u = bfs[pos % (k + 1)].front();
bfs[pos % (k + 1)].pop();
--num;
if (used[u]) // used vertex can be in other queues
{
continue;
}
used[u] = true;
for (pair<int, int> edge : g[u])
{
int cost = edge.first, w = edge.second;
if (d[u] + cost < d[w])
{
d[w] = d[u] + cost;
bfs[d[w] % (k + 1)].push(w);
++num;
}
}
}


It is easy to understand, that time complexity of this algorithm is O(N*K + M), because after analyzing each vertex we can increase pos only K times, also we have to remember about M edges.

That's all, hope you enjoyed!

P.S. Sorry for my bad English, if you find any mistake, please, contact me. #bfs, bfs, Comments (14)
 » I believe this is also known as Dial's algorithm. There is a mention of it in the cp-algorithms article on 0-1 bfs, however I don't think there was a good tutorial on it anywhere until this blog.
•  » » I am glad to hear it!
 » The author says "but restrictions do not allow us to use Dijkstras". Why can't we use Dijkstra to solve this ? Can someone explain ? What restrictions are making Dijkstras inapplicable here ?
•  » » Too slow.
•  » » » Thank you!
 » Sorry, if the question might be too obvious but why aren't we initializing pos to 0 after the while loop. Isn't it possible that for some vertex d[w]=d[u]+cost(w's value) will lead to some weight whose modulo (k+1) is less than it's current value(u's value)?
•  » » 12 months ago, # ^ | ← Rev. 3 →   You don't need to write modulo when you count d[i] value for any i. It is needed only not to hold N*K queues in the vector. And yes, you don't need to set pos = 0 after the while loop.
 » Cool algorithm. Another nice trick for graphs with small non-negative integer edge weights is given here. We can generalize the weights to $K$ instead of $2$. Edges with weights $0$, we can just join the two vertices into one. Then we perform normal BFS. Time complexity is the same as the above algorithm but it's probably more implementation.
 » 12 months ago, # | ← Rev. 2 →   Can someone explain the last part as to why array size of k + 1 will suffice. As to what I understood is that the algorithm is just like dijkstra, but here finding the vertex with lowest distance takes O(k) time, which makes it faster and also possible for low values of k.
•  » » Imagine that you haven't analyzed vertexes u, v such that d[u] is minimal and d[v] is maximal from possible. You can notice that d[v] — d[u] <= k. If not, we had to push v to queue when we were analyzing some vertex w such that d[w] > d[u] — contradiction (because in this case we've already deleted u from queue). Because of that, we need only k + 1 queues.
 » If you want to check an alternative implementation that also works for $0$-weighted edges (edge costs in range $[0..lim)$) and is quite compact, this is what I've written for our ICPC notebook. Complexity is $O(V + E + maxd)$ (bounded by $O(V \cdot lim + E)$). template vector SmallDijkstra(Graph& graph, int src, int lim) { vector> qs(lim); vector dist(graph.size(), -1); dist[src] = 0; qs.push_back(src); for (int d = 0, maxd = 0; d <= maxd; ++d) { for (auto& q = qs[d % lim]; q.size(); ) { int node = q.back(); q.pop_back(); if (dist[node] != d) continue; for (auto [vec, cost] : graph[node]) { if (dist[vec] != -1 && dist[vec] <= d + cost) continue; dist[vec] = d + cost; qs[(d + cost) % lim].push_back(vec); maxd = max(maxd, d + cost); } } } return dist; } 
 » Can someone provide links to questions based on this algorithm?Thanks
 » 3 months ago, # | ← Rev. 3 →   Thank you for such a great blog. I have two doubts. Doubt-1: Can anyone explain why time complexity N*K + M and not N*(K + M)? As the last for loop is in while loop hence I think it should be N*(K + M) not N*K + M. Doubt-2: Also, I think time complexity should be something like N*K + H, where H denotes total relaxations. Please correct if I am wrong.
•  » » 3 months ago, # ^ | ← Rev. 3 →   The inner relaxation loop will run for a vertex only if $used[vertex] = false$.This means that in the worst case, the relaxation loop will run for all the vertices. This has a time complexity of $\mathcal{O}(E)$. Since, it's equivalent to $\sum_{v\in V} {deg[v]} = 2 * E$Another way to think it is that each edge will be used at most twice in relaxation (Let $E = (u, v)$, then once while relaxing neighbors of $u$ and once again for relaxing neighbors of $v$).