Yukuk's blog

By Yukuk, 3 months 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 months 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.

»
3 months 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 ?

»
3 months 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)?

  • »
    »
    5 weeks 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.

»
3 months 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.

»
5 weeks 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.

  • »
    »
    5 weeks 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.

»
5 weeks 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;
}
»
5 weeks ago, # |
  Vote: I like it +11 Vote: I do not like it

Can someone provide links to questions based on this algorithm?

Thanks