himanshujaju's blog

0-1 BFS [Tutorial]
By himanshujaju, history, 9 years ago, In English

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 :

  1. Remove Top Element (To get vertex for BFS)
  2. Insert At the beginning (To push a vertex with same level)
  3. 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 :

  1. Can we apply the same trick if our edge weights can only be 0 and x (x >= 0) ?
  2. Can we apply the same trick if our edge weights are x and x+1 (x >= 0) ?
  3. 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 :

  1. http://www.spoj.com/problems/KATHTHI/ — My implementation
  2. https://community.topcoder.com/stat?c=problem_statement&pm=10337
  3. 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!

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

Comments Comments (80)
| Write comment?
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by himanshujaju (previous revision, new revision, compare).

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

Hi everyone!

You may solve problem J from here.

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

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

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

    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.

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

Really nice tutorial! I am waiting for more :)

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

for the first question it's clearly yes, but for second and third ones I think the answer is no, am I right?

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

    Yes.

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

      Can you please explain why is it NO for the second question? Also, if it is NO, should it be x>0?

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

        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]

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

          Okay, got it. Thanks.

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

          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?

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

      How about if edge weights are 1 and m+1, (m is the number of edges)

      would it work?

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

        NO. 3rd question.

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

          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)

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

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.

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

    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.

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

      Got it! Thanks.

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

      Your statement is not always true I think. Consider this triangular graph with all edge weight as $$$1$$$.

      (r)__1__(u)__1__(v)
 \               /
  \______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?

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

        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.

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

          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:

          (r)___1___(u)___1___(v)
 \                   /
  \___1___(t)___0___/

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

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

            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.

            (r)___1___(u)___1___(v)
 \                   /
  \___1___(t)___0___/

            Cool, it works, thanks!

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

Added Sample Implementation. Auto comment: topic has been updated by himanshujaju (previous revision, new revision, compare).

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

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.

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

    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?

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

      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.

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

        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?

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

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

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

            Oh yes, this thing works. Some people implement 0-1 BFS in this way!

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

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, G0 and G1 (for edges of cost 0, and 1, respectively). Then the algorithm is as follows:

  • Step 1: Add the source vertex to the graph. Mark it as visited
  • Step 2: Take the front of the queue and do a DFS through G0, marking any unvisited nodes and updating the corresponding distance. Add the unvisited adjacent nodes (through G1 this time) to the back of the queue
  • Step 3: Repeat Step 2 while the queue is not empty.

The C++ code is as follows:

void dfs(int node) {
   //Traverse through the 0-connected component
   for(auto v : G0[node])
      if(!Seen[v]) {
         Seen[v] = 1;
         D[v] = D[node];
         dfs(v);
      }
   //Push the unvisited 1-cost neighbours
   for(auto v : G1[node])
      if(!Seen[v]) {
         Seen[v] = 1;
         D[v] = D[node] + 1;
         Q.push(v);
      }
}

void bfs1_0(int start) {
   Q.push(start);
   Seen[start] = 1;

   while(!Q.empty()) {
      int top = Q.front();
      Q.pop();
      dfs(top);
   }
}

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.

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

    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 )

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

    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!

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

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.

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

I think it can also be solved with FloydWarshall or BellmanFord.

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

    You can even solve with a recursive brute force!

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

      But it is too slow. The algorithms I wrote are known good algorithms.

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

        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

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

Can anyone offer some more problems.I would be very appreciate.

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

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.

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

Great! I learned something new today.

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

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?

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

    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.

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

      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

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

      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?

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

        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.

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

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.

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

    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?

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

Sol Link https://ideone.com/h4CWcZ Question Link https://www.spoj.com/problems/KATHTHI/ Can someone please explain why this one getting TLE. Thanks :)

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

    You can do vis[x][y]=1; while pushing into a queue, not while popping from a queue.

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

Hi, You may also solve problem D from Codeforces #516 for practice.

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

why dont we need visited array to proceed with only those which are unvisited in o-1 bfs problem??

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

    Because you need to visit the node if the current cost is better, so instead of 

    if (!visited[u]) {
    // process node u
}

    You use

    if (dist[u] > dist[v] + cost[v][u]) {
    dist[u] = dist[v] + cost[v][u];
    // process node u
}
    → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
5 years ago, # |
  Vote: I like it -8 Vote: I do not like it

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

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

    if travelling e relaxes distance to u: This line of code helps us not to visit the visited vertex again.

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

      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

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

        Deleted

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

          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?

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

            Complexity remains unchanged though. The other 3 which is back in dequeue will not add any popped out vertex.

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

            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.

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

Can we use the trick, if y > |E|*x ?

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

Please tell me why I am getting TLE. code:- https://rextester.com/ESCXK71163

question

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

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.

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

    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.

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

Another great problem from recent Atcoder round

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

    Did you mean problem D?

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

      Ooops, my baddd. Thanks a lot for pointing it out.

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

THE VIDEO LINK IS HERE GUYS https://www.youtube.com/watch?v=cMP1IaWuFuM

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

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".

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

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?

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like 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.

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

Two Simple Problems at Atcoder.

Stronger Takahashi

Wizard in Maze

→ Reply