Yukuk's blog

[Tutorial] 1-K BFS
By Yukuk, 3 years ago, translation, In English

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[0].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.

  • Vote: I like it
  • +229
  • Vote: I do not like it

»
3 years ago, # |
  Vote: I like it +82 Vote: I do not like it

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.

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like 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 ?

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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)?

→ Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +6 Vote: I do not like it

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.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
3 years ago, # |
  Vote: I like it +16 Vote: I do not like it

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<typename Graph>
vector<int> SmallDijkstra(Graph& graph, int src, int lim) {
  vector<vector<int>> qs(lim);
  vector<int> dist(graph.size(), -1);

  dist[src] = 0; qs[0].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;
}
→ Reply
»
3 years ago, # |
  Vote: I like it +11 Vote: I do not like it

Can someone provide links to questions based on this algorithm?

Thanks

→ Reply
»
2 years ago, # |
← Rev. 3   Vote: I like it +1 Vote: I do not like it

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.

→ Reply
  • »
    »
    2 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    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$$$).

    → Reply
»
6 months ago, # |
← Rev. 3   Vote: I like it -11 Vote: I do not like it 
if (used[u]) // used vertex can be in other queues
{
	continue;
}
used[u] = true;

This part seems to be wrong, even if the vertex u is used in some other queue, its distance from the other vertex can be minimised just like we consider it in normal dijkstra algorithm.

Counter Case : now if we find the distance from node 1 to 4 using the given algorithm then distance from node 1 to 4 will be 4 (1-2-4) but the optimal answer is 3 (1-3-4)

graph

→ Reply
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can you use the algorithm with edges weights zero?(sorry for my bad english)

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

    Honestly i think its can but i just not sure

    → Reply