Link To PDF version (Latex Formatted)
Topic : 0-1 BFS
Pre Requisites : Basics of Graph Theory , BFS , Shortest Path
Problem :
You have a graph G with V vertices and E edges. The graph is a weighted graph but the weights have a contraint that they can only be 0 or 1. Write an efficient code to calculate shortest path from a given source.
Solution :
Naive Solution — Dijkstra's Algorithm.
This has a complexity of O(E + VlogV) in its best implementation. You might try heuristics , but the worst case remains the same. At this point you maybe thinking about how you could optimise Dijkstra or why do I write such an efficient algorithm as the naive solution? Ok , so firstly the efficient solution isn't an optimisation of Dijkstra. Secondly , this is provided as the naive solution because almost everyone would code this up the first time they see such a question , assuming they know Dijkstra's algorithm.
Supposing Dijkstra's algorithm is your best code forward , I would like to present to you a very simple yet elegant trick to solve a question on this type of graph using Breadth First Search (BFS).
Before we dive into the algorithm, a lemma is required to get things crystal clear later on.
Lemma : "During the execution of BFS, the queue holding the vertices only contains elements from at max two successive levels of the BFS tree."
Explanation : The BFS tree is the tree built during the execution of BFS on any graph. This lemma is true since at every point in the execution of BFS , we only traverse to the adjacent vertices of a vertex and thus every vertex in the queue is at max one level away from all other vertices in the queue.
So let's get started with 0-1 BFS.
0-1 BFS :
This is so named , since it works on graphs with edge weights 0 and 1. Let's take a point of execution of BFS when you are at an arbitrary vertex "u" having edges with weight 0 and 1. Similar to Dijkstra , we only put a vertex in the queue if it has been relaxed by a previous vertex (distance is reduced by travelling on this edge) and we also keep the queue sorted by distance from source at every point of time.
Now , when we are at "u" , we know one thing for sure : Travelling an edge (u,v) would make sure that v is either in the same level as u or at the next successive level. This is because the edge weights are 0 and 1. An edge weight of 0 would mean that they lie on the same level , whereas an edge weight of 1 means they lie on the level below. We also know that during BFS our queue holds vertices of two successive levels at max. So, when we are at vertex "u" , our queue contains elements of level L[u] or L[u] + 1. And we also know that for an edge (u,v) , L[v] is either L[u] or L[u] + 1. Thus , if the vertex "v" is relaxed and has the same level , we can push it to the front of our queue and if it has the very next level , we can push it to the end of the queue. This helps us keep the queue sorted by level for the BFS to work properly.
But, using a normal queue data structure , we cannot insert and keep it sorted in O(1). Using priority queue cost us O(logN) to keep it sorted. The problem with the normal queue is the absence of methods which helps us to perform all of these functions :
- Remove Top Element (To get vertex for BFS)
- Insert At the beginning (To push a vertex with same level)
- Insert At the end (To push a vertex on next level)
Fortunately, all of these operations are supported by a double ended queue (or deque in C++ STL). Let's have a look at pseudocode for this trick :
for all v in vertices:
dist[v] = inf
dist[source] = 0;
deque d
d.push_front(source)
while d.empty() == false:
vertex = get front element and pop as in BFS.
for all edges e of form (vertex , u):
if travelling e relaxes distance to u:
relax dist[u]
if e.weight = 1:
d.push_back(u)
else:
d.push_front(u)
As you can see , this is quite similar to BFS + Dijkstra. But the time complexity of this code is O(E + V) , which is linear and more efficient than Dijkstra. The analysis and proof of correctness is also same as that of BFS.
Before moving into solving problems from online judges , try these exercises to make sure you completely understand why and how 0-1 BFS works :
- Can we apply the same trick if our edge weights can only be 0 and x (x >= 0) ?
- Can we apply the same trick if our edge weights are x and x+1 (x >= 0) ?
- Can we apply the same trick if our edge weights are x and y (x,y >= 0) ?
This trick is actually quite a simple trick, but not many people know this. Here are some problems you can try this hack at :
- http://www.spoj.com/problems/KATHTHI/ — My implementation
- https://community.topcoder.com/stat?c=problem_statement&pm=10337
- Problem J of Gym
Div1 — 500 on topcoder are tough to crack. So congrats on being able to solve one of them using such a simple trick :). I will add more problems as I find.
Happy Coding!
P.S. : My first attempt at a tutorial. Please suggest edits wherever required!
Auto comment: topic has been updated by himanshujaju (previous revision, new revision, compare).
Hi everyone!
You may solve problem J from here.
Thanks , added to the list.
Nice tutorial! Just a comment:
This has a complexity of O(ElogV) in its best implementation. You might try heuristics , but the worst case remains the same
The worst case time complexity of Dijkstra's algorithm is O(E + V log V), using Fibonacci heaps. In contest problems, this can actually perform worse than the typical O(E log V) implementation, but the theoretical complexity is still O(E + V log V).
Thanks. I didnt actually know about the Fibonacci Heap implementation, will read up on that. I wrote it as O(ElogV) considering that everyone implements the priority_queue method in contests. Edited the post accordingly.
Really nice tutorial! I am waiting for more :)
for the first question it's clearly yes, but for second and third ones I think the answer is no, am I right?
Yes.
Can you please explain why is it NO for the second question? Also, if it is NO, should it be x>0?
Firstly, x >= 0 is given to specify the general case when x is non negative (Similar to dijkstra constraints).
You might think subtracting x will reduce it to a 0-1 BFS problem , but let's suppose the graph is like :
1 -> 2 (weight x)
2 -> 3 (weight x)
1 -> 3 (weight x + 1)
For source = 1 and destination = 3 :
0-1 BFS gives us minimum distance by traversing the two 0 edges , while we should traverse the 1 edge to get minimum distance. [0 edges means edges with weight x , 1 edges means edges with weight x + 1]
Okay, got it. Thanks.
But since you've put that relaxation condition it'll always maintain the least distance for a vertex right? So I guess it'll work for any graph with just two kind of weights. Am I missing something?
Update: My bad. I got it where it'd fail.
How about if edge weights are 1 and m+1, (m is the number of edges)
would it work?
NO. 3rd question.
I know it's the third question, but are you sure it fails for ALL cases of the third question? eg. it would most likely 'YES' for weights: 1 and 1e9. So i'm asking if it could work for all weights of type 1 and x(x>m)
3rd Question Answer
Ohh, i see now. Thanks
I didn't get this part, specially the bolded one:
"Now , when we are at "u" , we know one thing for sure : Travelling an edge (u,v) would make sure that v is either in the same level as u or at the next successive level. This is because the edge weights are 0 and 1. An edge weight of 0 would mean that they lie on the same level , whereas an edge weight of 1 means they lie on the level below."
Could you elaborate a bit more?
Thanks.
Consider the level here as distance from the root. For an edge weight 0 , the distance remains the same and for an edge weight 1, the distance increases by one.
Got it! Thanks.
Your statement is not always true I think. Consider this triangular graph with all edge weight as $$$1$$$.
Suppose $$$(r)$$$ is root, and we start bfs. Then suppose $$$(u)$$$ is first added to queue and then $$$(v)$$$ so the queue is $$$[u, v]$$$. The edge $$$(u, v)$$$ has weight $$$1$$$ but $$$u, v$$$ are on same level in BFS tree as both have distance $$$1$$$ from root.
Am I missing something?
Well in this particular case both $$$(u)$$$ and $$$(v)$$$ are added to the queue immediately. $$$(v)$$$'s distance from the root will thus have been established to be $$$1$$$ at the very beginning, so the "if relaxes" condition in the program won't be satisfied, and $$$(v)$$$ will not be added to the deque again from $$$(u)$$$.
However, let's say instead of having an edge weight of 1 between $$$(r)$$$ and $$$(v)$$$, there was an edge weight of $$$1$$$ from $$$(r)$$$ to a new node $$$(t)$$$ and an edge weight of $$$0$$$ from $$$(t)$$$ to $$$(v)$$$. (by the way how did you add that graph in your post; I can't get the newlines and spaces nicely like that)
Then yes, the program will initially treat $$$(v)$$$ as being on a different level than $$$(u)$$$, instead of the same level (aka distance $$$1$$$ from the root). But that's not a problem, because before $$$(v)$$$ is considered, $$$(t)$$$ will be considered, and then the better distance to $$$(v)$$$, which is $$$1$$$, will be added to the front of the deque. Thus the $$$(v)$$$ which is found through the path $$$(r)-(t)-(v)$$$ will be taken out of the deque before the $$$(v)$$$ from the path $$$(r)-(u)-(v)$$$, and so the correct answer will be found.
I think what was meant was that the program will initially perceive the two on successive levels, and add neighbors to the deque accordingly, and could later find out that it was 'wrong' through relaxation from other paths, in which case the 'better' version will be added to the front of the deque and considered before the 'wrong' version.
I think I didn't consider the relaxing part of explanation, but you explained well! I used code formatting (enclose the block in pair of ```) so the graph formats as code and sits in between lines. Your example graph:
So the point overall is that in your graph node $$$u$$$ has made sure that $$$v$$$ is in its next layer (at least) and node $$$t$$$ has ensured that $$$v$$$ is in its same layer. And so from your last paragraph, in this case
if $$$u$$$ got pushed before $$$t$$$ then one $$$v$$$ will be pushed to back of queue due to $$$r-u-v$$$ path and one queue to front due to $$$r-t-v$$$
if $$$t$$$ got pushed before $$$u$$$ then $$$t$$$ will be popped first so $$$v$$$ will get relaxed and get pushed to front.
Am i correct!?
Yup! I believe a node can be added twice to the deque, but not more.
I guess one can maintain an array of visited nodes, but that shouldn't change the complexity.
Cool, it works, thanks!
Added Sample Implementation. Auto comment: topic has been updated by himanshujaju (previous revision, new revision, compare).
A similar but more general technique that can correctly deal with questions 2 and 3 is as follows.
Maintain a minimum priority queue of tuples with type (distance from source, queue of vertices having this distance). Proceed with a normal BFS, however, only pop from the queue with minimum distance until it is exhausted, then move to the next smallest. This is O(V+E) given a limited number of weights. In fact, I believe in the worst case its time complexity is bounded by O(V + E * lg(#distinct_edge_weights)). [nonsense]There should only be W(W+1)/2 elements in the priority queue at any given point in time, where W is the number of distinct edge weights.[/nonsense] Notice that this can have significantly larger constant factors as compared to running Dijkstra's algorithm, but for a small set of distinct edge weights, is should have low constant factors and superior asymptotic performance.
There's a good chance I have made a mistake as I derived this on the spot while typing. Please be nice.
Is the priority queue tuple of the form pair<distance , queue > ? Could you explain why the log factor has only number of distinct edge weights?
Yes.
I've thought about it more (my first post was very hasty), and now I tentatively claim that you need only #distinct_edge_weights queues, and the next vertex we visit is the minimum element from the head of any queue. We insert elements onto the end of the queue corresponding to the edge weight we just traversed to get there.
Suppose edge weights are 3 and 5. Initially we have two queues for distance 3 and 5. Now by iterating vertices at distance 3 , we can get two more queues for distance 6 and 8. Now, we have queues for distance (5,6,8). After iterating or 5, we have (6,8,10) and after iterating for 6, we have (8,9,10,11) which is greater than W*(W+1)/2. Or did I understand your claim incorrectly? Also, is sorting the priority queue O(logN) when we have a queue in the tuple or it increases?
I think you've misunderstood my response. My first post is 50% gibberish, please ignore it for the purposes of understand what I am talking about haha.
In that case there will only be two queues. One for weight 3, and one for weight 5. As I have said, the algorithm works like this. Create a queue for each distinct weight. Queue elements are a tuple of (distance traveled, current vertex). Now we run a modified BFS. While there is an element on any queue, find the queue with the minimum head element, pop it, then process it. When we wish to push a child to one of the queues, we will have just traversed an edge to get to the child we are pushing. Push the child to the queue corresponding to the weight of the edge we traversed.
I think this can be shown to always work. The reason I think it works is that all the queues will be in monotonically increasing order of distance. To prove this, let's postulate that, for some reason, they are not in increasing order. For this to be the case, there must be an element E of a queue such that its direct predecessor P in the same queue was greater, that is E < P. Let's assume that this is the first such inversion that our algorithm has produced for the sake of simplicity. Note that P and E are on the same queue, so they must both have ended with the same edge weight. Now, consider that when we popped off the prefix to E (the sub-path minus the last edge), it was on the front of some queue. The same must have been true for the prefix of P. They may have been on different queues. Now observe that prefix(E) < prefix(P). If both were on the front of queues, then we couldn't possibly have picked prefix(P) first, as we always pick the minimum element. So we must have picked some element that was earlier in the same queue as prefix(E). However, since we said that this is the first inversion that happened, all such queue elements must be <= prefix(E), so we would have had to have made the choice between prefix(P) and prefix(E) at some point. This leads to a contradiction: we couldn't possibly have picked prefix(P) before prefix(E), thus our queues are always in increasing order. (It's very likely I've made a mistake as I did in my first post, so definitely consider this and come to your own conclusions.)
Oh yes, this thing works. Some people implement 0-1 BFS in this way!
I would like to propose an alternative algorithm to what you said, that seems easier to me:
We keep a regular queue (just like regular bfs), and also two graphs,
G0andG1(for edges of cost0, and1, respectively). Then the algorithm is as follows:G0, marking any unvisited nodes and updating the corresponding distance. Add the unvisited adjacent nodes (throughG1this time) to the back of the queueThe C++ code is as follows:
You can easily prove that the queue Q will always be sorted by the distances, so, in essence, the algorithm cannot produce a different output than Dijkstra's.
For the next graph:
Calling bfs1_0(0), your algorithm produce distance 1 for node 3, but it should be 0.
(Sorry for my poor(and horrible) english. xD )
I just found out that this implementation fails in this case.
Here, if source = 1, then the minimun distance of node 8 comes to be 2 but it should be 1(1 -> 2 -> 5 -> 8)
UPD — I think there is only a single mistake in your code. Instead of checking a node if seen, we need to check whether that node is getting relaxed by distance. I rectified it and then this implementation worked!
Another way to speed up the shortest path from a given source on a graph with small weights (not necessary to be 0 and 1) would be Dial's Algorithm (also known as Dijkstra with buckets), which runs in O(V * C + E) time and memory (considering the notations made by op and C the maximum weight of an edge).
Here you have a presentation of the algorithm.
LE: I belive this is what SustainedScreaming was talking about.
I think it can also be solved with FloydWarshall or BellmanFord.
You can even solve with a recursive brute force!
But it is too slow. The algorithms I wrote are known good algorithms.
So dont you think this technique is faster than what you wrote? Sorry if I am being arrogant and idiotic but its all part of the handle :D
Can anyone offer some more problems.I would be very appreciate.
11573 — Ocean Currents
28. Error
B. Chamber of Secrets
Another problem is 590C - Three States
Valentines Day
A more recent problem from Codeforces round 637:
Nastasya and Unexpected Guest
It should be pointed out that the algorithm described will sometimes push the same node on the queue twice which makes it somewhat unlike the usual BFS.
Great! I learned something new today.
himanshujaju can we replace this condition in pseudocode "if travelling e relaxes distance to u:" by just checking whether u vertex has been already visited or not because i think only for this 0-1 BFS case it will always be atmost one time that this condition ("if travelling e relaxes distance to u:") will be true. Am i right?
I don't think that's true, it can be more than one time. It's not that tough to construct a graph for that. Also, I intended to write in that fashion so that it is similar to dijkstra with a different underlying data structure.
is it exactly similar to dijkstra(as i have perceived) we are just neglecting that log(n) factor by using deque to maintain the priority of topmost element to be extracted in each iteration of loop, am i getting right(i have submitted first problem with this logic which is accepted)?
please explain a bit about problem3 , i have found a way but that may time out
himanshujaju yes i can understand your intention its absolutely right.
It's just that i have come to above point of replacing this condition "if travelling e relaxes distance to u:" by just checking whether u vertex has been already visited or not, because this if condition is only true for any node (u) only once because since we are keeping the queue sorted by distance from source at every point of time, so after encountering true for the first time in if condition for a node u, thereafter it will not be possible for that node(u) to have minimum distance(it may be equal but not less than that) than that of what we have encountered when if condition was true for the first time.
Or can you give me some example/test case for which my above assumption fails?
If by visited you mean the time when we explore the neighbours of a vertex, then that is only once (just like dijkstra). Otherwise, if you mean that we relax the distance exactly once then the following case can help you out (assuming the same pseudocode) :
You have 3 vertices, edges are : 1 -> 2 (cost 0), 2 -> 3 (cost 0) and 1 -> 3 (cost 1). If my source is 1, I will relax cost of 3 to 1 first (from infinity) and then relax it again to 0 (from 1) when I visit it from 2. So we relax the distance twice.
Why bother with BFS? Queues are ugly. You can just run dfs with recursion and complexity will be O(V * E) in the worst case.
All data structures are beautiful; we don't establish discriminatory standards here on Codeforces. We need to end the horrific node-shaming, ableist views of competitive programmers. Just because it isn't recursion doesn't mean it's not beautiful, ok?
Sol Link https://ideone.com/h4CWcZ Question Link https://www.spoj.com/problems/KATHTHI/ Can someone please explain why this one getting TLE. Thanks :)
You can do
vis[x][y]=1;while pushing into a queue, not while popping from a queue.Hi, You may also solve problem D from Codeforces #516 for practice.
why dont we need visited array to proceed with only those which are unvisited in o-1 bfs problem??
Because you need to visit the node if the current cost is better, so instead of
You use
Here is another one from LeetCode — https://leetcode.com/problems/minimum-moves-to-move-a-box-to-their-target-location/
Like SustainedScreaming said we can use two queues to increase performance since deque is slower than queue. My solution using the same idea.
Why don't we need a visited array? Because if we have explored the neighbors of a vertex then we don't need to explore it again but in the above algorithm we are exploring it as many times as it was added in the queue which can increase the time complexity.Am I thinking something wrong?himanshujaju
if travelling e relaxes distance to u: This line of code helps us not to visit the visited vertex again.
But this line (if traveling e relaxes distance to u) can occur many times and it will add vertex u to dequeue many times. newStartNotSure
Deleted
Consider the following example
V={1,2,3} and E={(1,2,0),(1,3,1),(2,3,0)}.It is (u,v,w). Let source be 1. Exploring 1, we will add 3(dis=1) and 2(dis=0) to the deque. After this, we will explore vertex 2. Now we will again add vertex 3(dis=0) to the deque. Is something wrong here?
Complexity remains unchanged though. The other 3 which is back in dequeue will not add any popped out vertex.
If initially any vertex is added in dequeue as dist[u], then it can be added again in dequeue if relaxing edge makes distance as dis[u]-1(it cannot make less than that). so any vertex cannot be added more than twice.
Thanks for the help.
Can we use the trick, if y > |E|*x ?
Please tell me why I am getting TLE. code:- https://rextester.com/ESCXK71163
question
Atcoder Problem — Snuke's Subway Trip Can someone tell if this problem is like 0-1 BFS because ci's are like 0 and 1 with respect to each other, and if yes then can u pls suggest the idea that how to do this question as neither I am able to do this question using 0-1 BFS nor using Dijkstra's.
Let's say you have edge between $$$u$$$ and $$$v$$$ operated by company $$$c$$$. Then construct node $$$(u, c)$$$ and $$$(v, c)$$$ . Now, there is edge between $$$(u, a)$$$ to $$$(v, b)$$$ if there is edge between $$$u$$$ and $$$v$$$ in original graph. weight is $$$0$$$ if $$$a = b$$$ otherwise $$$1$$$. Now, simply apply 0-1 BFS.
Another great problem from recent Atcoder round
Did you mean problem D?
Ooops, my baddd. Thanks a lot for pointing it out.
THE VIDEO LINK IS HERE GUYS https://www.youtube.com/watch?v=cMP1IaWuFuM
Am I right in saying this — "Whenever we pop a vertex from the $$$deque$$$, we can be assured that it is the one with the shortest distance from the $$$root$$$. So, we can run the $$$bfs$$$ for $$$|V|$$$ iterations, rather than until the $$$deque$$$ is empty".
I heard that it could also work on edge weights as long as one of them is 0. Like 0/1 BFS could work on edge weights 0 and 5. Is this true? Can someone confirm it?
Yes! As u can see he shared 3 true/false kinds of problems of which answers are(1-true,2-false,3-false) only 1st statement follows this rule- of having one of the edge weight as 0.
Two Simple Problems at Atcoder.
Stronger Takahashi
Wizard in Maze
is it useful in modern cp ?