professorbrill's blog

BFS on 0-1 graph
By professorbrill, 12 years ago, In English

Given a weighted digraph with weights either 0 or 1 find the shortest path. I heard that it can be solved using BFS and deque. But I don't really know how to prevent an vertex from appearing in the deque several times. Which condition on adding them to deque should I add? Thanks.

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

Comments Comments (8)
| Write comment?
»
12 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

First of all you can use queue for bfs, not deque.

Try to use bool array was[] for all vertexes.

was[x] == 1 — you've already added a vertex x to queue. And you should add a vertex to queue only if was[x] != 1

UPD: Sorry, I didn't notice 0,1 weights. In this case you should add a vertex only if shortest distance to it has changed. Or use was[] array and if you've got to vertex by an edge with 0 weight — add it to head of deque else tail.

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

Just store the distance from the source:

int distance[MAXN];

First, initialize to infinity all the distances:

#include <limits>
fill(distance, distance+MAXN, numeric_limits<int>::max());

Then, initialize to zero the distance from the source:

distance[source] = 0;

So, whenever you have to decide whether to add or not a neighboring node to the deque, you will first check if the distance found so far for that node is worse than the one you are proposing now:

if (distance[neighbor] > distance[node] + edge_weight) // edge_weight is 0 or 1

If that conditions evaluates to true, you will add that node to the deque (to the front if edge_weight is 0, to the back if it is 1) AND you will update the distance to that node with the value you proposed.

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

    but according to your code it seems to me that one vertex can still appear in your deque several times :-)

    UPD: can you prove to me please that one vertex won't appear in the deque twice?

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

      Yes, a node can appear twice:

      1 -> 2 (w = 1)
1 -> 3 (w = 0)
3 -> 2 (w = 0)

      The deque operations:

      push 1
pop 1
push 2
push 3
pop 3
push 2 // (now 2 appears twice)
...

      I think you shouldn't worry too much about it, because the second time you pop a node from the deque the "if" condition on its neighbors will always fail, and you will drop that node. If you are really worried, you can change the deque<int> to a deque< pair<int,int> > so you can store the distance of the node: in this way the previous deque operations become:

      push 1, d = 0
pop 1 // dist = 0
push 2, d = 0 + 1 = 1
push 3, d = 0 + 0 = 0
pop 3 // dist = 0
push 2, d = 0 + 0 = 0 // you have (2,1) pair and (2,0) pair in the deque
pop 2 // dist = 0
// there aren't neighbors
pop 2 // dist = 1, so we drop it
// now deque is empty

      Having this information, you can decide whether to drop or not the node right after popping it from the deque:

      int node = deque.front().first, dist = deque.front().second;
deque.pop();
if (dist > distance[node]) // you can drop this node
else // try to expand to neighbors, as usual

      This way you can avoid looking all the neighbors before dropping the node.

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

When you do a normal BFS only with 1-weight edges note that nodes are always inserted into the queue sorted by distance, so every time you pop a node it will be one of the "closest". When you have 0-weight and 1-weight edges you should insert nodes also sorted by distance. Suppose you have popped a node U with distance D, then you try to insert its adjacent nodes, note that an adjacent node of U with 0-weight will have the same distance D of U, so it should be "processed" (popped) before any other nodes with distance D + 1. To ensure that you push it in the front of the deque, so the next node you pop will be one with distance D (because you pop nodes from the front). Adjacent nodes with 1-weight edges should be pushed in the back of the deque as in a normal BFS. Pushing nodes in the front or back, you guaranteed that all nodes with distance D are processed before nodes with distance D + 1. So each node will be pushed and popped at most once, so it is O(V + E).

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

step1: Try to go through 0-edges only. when you can't anymore go to step2

step2: visit only one node using 1-edge and back to step1

stop when you visit all nodes or you can't anymore visit a new node(in case of not connected graph)

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

    I think it's important which node in step 2 you choose and it is not that easy to chose it, so you can't just state: "visit one node using 1-edge", because it doesn't always bring you to the right answer. You just don't know what edges come next and if you start checking that the solution can become really slow

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

      ok, you choose the 1-edge such that you are going from a node which the number of 1-egdes used to come to this node is minimal

      → Reply