Hello all, sorry for this lame doubt, but I could not find any answer online.
Why is it that when implementing a 0-1 BFS, a visited array isn't necessary, while in Dijkstra it is necessary. According to cp-algorithm for dijkstra,
"Therefore we need to make a small modification: at the beginning of each iteration, after extracting the next pair, we check if it is an important pair or if it is already an old and handled pair. This check is important, otherwise the complexity can increase up to O(nm)."
Shouldn't the same be applicable to 0-1 BFS also? And if not, why do we require it for Dijkstra?
If we implement Dijkstra with a
priority_queue, we usually only have methods likeadd(),poll(), andgetMin(), therefore we need a way to know if a vertex has been handled before, otherwise in certain situations, time complexity ofpriority_queueimplementation can go upto O(n*m). I think the same can be extended to 0-1 BFS if we use a deque implementation of 0-1 BFS.Notice if we implement Dijkstra with a
STL set, we don't need a visited array, since set has method to modify certain values while still maintaining the invariant of being sorted, and therefore, we can implement the 0-1 BFS with a set as well.Hey, thanks for the reply! But I've saw people implement 0-1 BFS without the visited array being used. Also, can you elaborate how not using a visited array in Dijkstra leads to O(n*m) time complexity?
Also, can you elaborate how not using a visited array in Dijkstra leads to O(n*m) time complexity
I am not sure how to quantify it that specifically, but you can notice that when we implement Dijkstra without a
priority_queue, we can push various instances of the same vertices, since regular STLpriority_queuedoesn't allow you to modify values and at each step we have to push a pair of the form<node_id, updated_dist>. All of this can lead to processing the same vertices multiple times than intendedI've saw people implement 0-1 BFS without the visited array being used.
I am not that sure, but I think if we use a visited array with a deque, we can potentially make it faster as well and I don't think it will make the algorithm wrong. After some research, I found out in a 0-1 BFS we cannot process a node more than two times, therefore, a visited array is not needed, per say.
Hey, thank you so much for your reply, 0-1 BFS will not process a node more than two times was a very useful insight!
You want to avoid situations like this.
You are processing a node as many times as you push into the heap, which is bad for high-degree vertices. It is easy to craft similar test cases without using multiple edges.
Strictly speaking, we don't need a "visited" array in implementation, as we can just use the distance array to check whether we've visited this node before. The point is that we need some structure to help us not process a node multiple times.
And for the 0-1 BFS it's just as xoringbitset said, there aren't too many times one node can get processed.
Hey, thank you so much for your reply, it is indeed a good example!