Пошук у ширину 0-1#10056

Пошук у ширину 0-1 (Розбір)

$0 - 1$ 0 - 1 пошук в ширину (або $0 - 1$ 0 - 1 BFS) — це модифікація класичного алгоритму пошуку в ширину (BFS), який використовується для знаходження найкоротших шляхів у графах. Відмінність цього алгоритму в тому, що ваги ребер у графі можуть приймати лише значення $0$ або $1$ , що дозволяє значно оптимізувати пошук.

Постановка задачі. Уявімо, що у нас є зважений граф, у якому ваги ребер — це або $0$ , або $1$ . Наприклад, такий граф можна зустріти, коли ми працюємо з містом, в якому деякі дороги безкоштовні (вага $0$ ), а за інші доводиться платити (вага $1$ ). Ми хочемо знайти найкоротший шлях від однієї вершини графа до іншої з урахуванням цих ваг.

Проблема стандартного алгоритму пошуку в ширину. Класичний алгоритм пошуку в ширину (BFS) має оцінку складності $O (V + E)$ O(V + E) і використовується для пошуку найкоротших шляхів у графі, але він підходить лише для графів, де всі ребра мають однакову вагу. У випадку, якщо ваги ребер різні, такий підхід вже неефективний — для цих цілей зазвичай застосовують алгоритм Дейкстри з оцінкою складності $O (V^{2} + E)$ O(V^2 + E) або $O (E \cdot l o g_{2} V)$ O(E \cdot log_2V). Але для графів з вагами лише $0$ і $1$ існує швидший підхід — $0 - 1$ 0 - 1 BFS.

0-1 BFS Алгоритм

У $0 - 1$ 0 - 1 BFS ми використовуємо двосторонню чергу (deque). Ідея полягає в наступному:

Ми починаємо з початкової вершини $s t a r t$ і додаємо її до черги з початковою відстанню, що дорівнює $0$ .
При обробці кожної вершини $u$ (яка витягується з голови черги) розглядаємо її сусідів $v$ :
- Якщо у ребра $(u, v)$ вага $0$ , то сусідня вершина $v$ поміщається на початок черги з поточною відстанню $(d i s t [v] = d i s t [u])$ (dist[v] = dist[u]).
- Якщо у ребра $(u, v)$ вага $1$ , то сусідня вершина $v$ поміщається в кінець черги зі збільшенням відстані на одиницю $(d i s t [v] = d i s t [u] + 1)$ (dist[v] = dist[u] + 1).
Це дозволяє ефективно підтримувати правильний порядок обробки вершин: вершини, досяжні через ребра з меншою вагою, обробляються раніше.

Таким чином, використання двосторонньої черги гарантує, що ми завжди маємо доступ до вершини з мінімальною відстанню на початку черги, а складність роботи алгоритму залишається $O (V + E)$ O(V + E).

Релаксація ребер при $0 - 1$ 0 - 1 пошуку в ширину схожа на класичну релаксацію в алгоритмі Дейкстри, але відрізняється використанням двосторонньої черги (deque) замість черги з пріоритетами (priority queue) для впорядкування вершин на основі ваги ребер.

Алгоритм $0 - 1$ 0-1 BFS (на відміну від класичного BFS) не гарантує, що кожна вершина буде відвідана з мінімальною відстанню з першого разу, особливо якщо до однієї й тієї самої вершини можна дістатися кількома шляхами. Тому релаксація ребер обов'язкова.

Розглянемо наступний приклад. Ініціалізуємо масив найкоротших відстаней $d i s t$ та чергу $q$ :

Розглянемо ребра, що виходять з вершини $1$ . Релаксуємо ребра $(1, 2)$ та $(1, 3)$ . Вершина $3$ буде занесена на початок черги, а вершина $2$ — у кінець черги.

Однак значення $d i s t [2] = 1$ dist[2] = 1 не є остаточним. Пройдемо по ребру $3 - 4$ 3 - 4 і встановимо $d i s t [4] = 0$ dist[4] = 0, $q u e u e = (4, 2)$ queue = (4, 2). Потім розглянемо ребро $4 - 2$ 4 - 2 і значення $d i s t [2]$ встановиться рівним $0$ . Таким чином, $d i s t [2]$ приймало два різних значення в результаті релаксації (спочатку $1$ , потім $0$ ).

Приклад

Граф, наведений у прикладі, має вигляд:

Довжина найкоротшого шляху з вершини $1$ у $3$ дорівнює $1$ , а сам найкоротший шлях має вигляд: $1 - 2 - 3$ 1 - 2 - 3.

Реалізація алгоритму

Оголосимо константу нескінченність.

#define INF 0x3F3F3F3F

Оголосимо масив найкоротших відстаней $d i s t$ і список суміжності графа $g$ .

vector\u003cint\u003e dist;
vector\u003cvector\u003cpair\u003cint, int\u003e\u003e\u003e g;

Функція bfs реалізує пошук у ширину з вершини $s t a r t$ .

void bfs(int start)
{

Ініціалізуємо масив найкоротших відстаней $d i s t$ .

  dist = vector\u003cint\u003e(n + 1, INF);
  dist[start] = 0;

Оголосимо чергу і занесемо в неї стартову вершину $s t a r t$ .

  deque\u003cint\u003e q;
  q.push_back(start);

Продовжуємо алгоритм пошуку в ширину, поки черга не порожня.

  while (!q.empty())
  {

Витягуємо з голови черги вершину $v$ .

    int v = q.front(); q.pop_front();

Перебираємо ребра, що виходять з вершини $v$ .

    for (auto edge : g[v])
    {
      int to = edge.first;
      int w = edge.second;

Поточне ребро $(v, t o)$ (v, to) має вагу $w$ . Проводимо його релаксацію.

      if (dist[to] \u003e dist[v] + w)
      {

Якщо ребро релаксує, то перераховуємо найкоротшу відстань $d i s t [t o]$ dist[to].

        dist[to] = dist[v] + w;

Залежно від ваги ребра $w$ додаємо вершину $t o$ в кінець або на початок черги.

        if (w == 1)
          q.push_back(to);
        else
          q.push_front(to);
      }
    }
  }
}

C++

Основна частина програми. Читаємо вхідні дані.

scanf("%d %d %d %d", \u0026n, \u0026m, \u0026s, \u0026d);
g.resize(n + 1);

Читаємо граф.

for (i = 0; i \u003c m; i++)
{
  scanf("%d %d %d", \u0026a, \u0026b, \u0026w);
  g[a].push_back({ b, w });
  g[b].push_back({ a, w });
}

Запускаємо пошук у ширину зі стартової вершини $s$ .

bfs(s);

Виводимо найкоротшу відстань до вершини $d$ .

printf("%d\n", dist[d]);