Блог пользователя professorbrill

BFS на 0-1 графе
Автор professorbrill, 12 лет назад, перевод, По-русски

Дан взвешенный ориентированный граф с ребрами с весами либо 0 либо 1. Найти кратчайший путь. Я слышал что эту задачу решают BFSом и деком, но не знаю как предотвратить добавление одной вершины в дек несколько раз. Какой условие надо поставить на добавление в дек? Спасибо.

  • Проголосовать: нравится
  • +6
  • Проголосовать: не нравится

»
12 лет назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

Когда вершина добавляется в дек с любой из сторон, нужно сохранить новое кратчайшее расстояние до нее. Соответственно, добавлять вершину нужно только если кратчайшее расстояние уменьшается. Таким образом каждая вершина будет добавлена не больше двух раз.

→ Ответить
  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    правильно я понимаю что у нас два массива bool? один для тех кого пихают спереди и другой для тех которых пихают сзади?

    → Ответить
    • »
      »
      »
      12 лет назад, # ^ |
      ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      Зачем массивы bool? Есть только массив текущих кратчайших расстояний. Если нашли путь короче, добавляем в нужную сторону дека, сразу же обновив кратчайшее расстояние. Доказательство, что вершина будет добавлена максимум два раза, вроде бы очевидно.

      Чтобы сократить время работы еще в два раза, можно добавлять пары (вершина, расстояние) и обрабатывать ее только тогда, когда расстояние = текущему кратчайшему.

      → Ответить
»
12 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

Обычный BFS, но если текущее ребро нулевой длины, то вершину надо добавить не в конец, а в начало дека. Так каждая вершина побывает в деке не более двух раз.

→ Ответить
»
12 лет назад, # |
← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

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.

→ Ответить
»
12 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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.

→ Ответить
  • »
    »
    12 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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?

    → Ответить
    • »
      »
      »
      12 лет назад, # ^ |
      ← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

      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.

      → Ответить
»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
»
12 лет назад, # |
← Rev. 2   Проголосовать: нравится -6 Проголосовать: не нравится

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)

→ Ответить
  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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

    → Ответить
    • »
      »
      »
      12 лет назад, # ^ |
      ← Rev. 2   Проголосовать: нравится -6 Проголосовать: не нравится

      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

      → Ответить
»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Можно было самому погуглить, раз уж это с контеста идущего задача.

→ Ответить
  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +10 Проголосовать: не нравится

    Что же это за контесты такие, где предлагают 100-летние бабаяны? В последнее время такие темы, кстати, стали очень популярны. Не кажется, что эти контесты очень серьёзные, если там предлагают совершенно классические задачи.

    → Ответить
    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится -6 Проголосовать: не нравится

      В этом году, честно говоря, действительно не очень серьезный по сравнению с прошлыми.

      → Ответить
»
12 лет назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

Лично я просто делаю две очереди для ребер весом 0 и 1 соответственно. В начале каждой итерации bfs-a берешь элемент из первой непустой очереди. Такая реализация хорошо обобщается на случай с 0-k графом(создаешь k очередей). А массивов used здесь не надо. Как при релаксации в дейкстре смотрим, улучшилось расстояние до вершины или нет. Если улучшилось, то добавляем вершину в соответствующую очередь. Не улучшилось — забиваем. Почему она будет добавлена не больше k+1 раз(в данном случае k+1=2) уже объяснили выше.

→ Ответить