B0JACK's blog

0-1 BFS and Dijkstra doubt
By B0JACK, history, 4 years ago, In English

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?

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

»
4 years ago, # |
← Rev. 3   Vote: I like it +13 Vote: I do not like it

If we implement Dijkstra with a priority_queue, we usually only have methods like add(), poll(), and getMin(), therefore we need a way to know if a vertex has been handled before, otherwise in certain situations, time complexity of priority_queue implementation 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.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    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?

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

      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 STL priority_queue doesn'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 intended

      I'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.

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

        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!

        → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +23 Vote: I do not like it

      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.

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

        Hey, thank you so much for your reply, it is indeed a good example!

        → Reply