Разбор

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

Постановка задачи. Представим, что у нас есть взвешенный граф, в котором веса рёбер — это либо $0$, либо $1$. Например, такой граф можно встретить, когда мы работаем с городом, в котором некоторые дороги бесплатные (вес $0$), а по другим приходится платить (вес $1$). Мы хотим найти кратчайший путь от одной вершины графа до другой с учётом этих весов.

Проблема стандартного алгоритма поиска в ширину. Классический алгоритм поиска в ширину (BFS) имеет оценку сложности $O(V+E)$ и используется для поиска кратчайших путей в графе, но он подходит только для графов, где все рёбра имеют одинаковый вес. В случае, если веса рёбер различны, такой подход уже неэффективен — для этих целей обычно применяют алгоритм Дейкстры с оценкой сложности $O(V^2+E)$ или $O(E\cdot lo{g}_{2}V)$. Но для графов с весами только $0$ и $1$ существует более быстрый подход — $0-1$ BFS.

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

В $0-1$ BFS мы используем двустороннюю очередь (deque). Идея состоит в следующем:

1. Мы начинаем с исходной вершины $start$ и добавляем её в очередь с начальным расстоянием, равным $0$.

2. При обработке каждой вершины $u$ (которая извлекается из головы очереди) рассматриваем её соседей $v$:

   • Если у ребра $(u,v)$ вес $0$, то соседняя вершина $v$ помещается в начало очереди с текущим расстоянием $(dist[v]=dist[u])$.

   • Если у ребра $(u,v)$ вес $1$, то соседняя вершина $v$ помещается в конец очереди с увеличением расстояния на единицу $(dist[v]=dist[u]+1)$.

3. Это позволяет эффективно поддерживать правильный порядок обработки вершин: вершины, достижимые через рёбра с меньшим весом, обрабатываются раньше.

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

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

Рассмотрим следующий пример. Инициализируем массив кратчайших расстояний $dist$ и очередь $q$:

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

Однако значение $dist[2]=1$ не является окончательным. Пройдем по ребру $3-4$ и установим $dist[4]=0$, $queue=(4,2)$. Затем рассмотрим ребро $4-2$ и значение $dist[2]$ установится равным $0$. Таким образом, $dist[2]$ принимало два различных значения в результате релаксации (сначала $1$, потом $0$).

Пример

Граф, приведенный в примере, имеет вид:

Длина кратчайшего пути из вершины $1$ в $3$ равна $1$, а сам кратчайший путь имеет вид: $1-2-3$.

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

Объявим константу бесконечность.

#define INF 0x3F3F3F3F

Объявим массив кратчайших расстояний $dist$ и список смежности графа $g$.

vector<int> dist;
vector<vector<pair<int, int>>> g;

Функция bfs реализует поиск в ширину из вершины $start$.

void bfs(int start)
{

Инициализируем массив кратчайших расстояний $dist$.

  dist = vector<int>(n + 1, INF);
  dist[start] = 0;

Объявим очередь и занесем в нее стартовую вершину $start$.

  deque<int> 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,to)$ имеет вес $w$. Проводим его релаксацию.

      if (dist[to] > dist[v] + w)
      {

Если ребро релаксирует, то пересчитываем кратчайшее расстояние $dist[to]$.

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

В зависимости от веса ребра $w$ добавляем вершину $to$ в конец или в начало очереди.

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

Основная часть программы. Читаем входные данные.

scanf("%d %d %d %d", &n, &m, &s, &d);
g.resize(n + 1);

Читаем граф.

for (i = 0; i < m; i++)
{
  scanf("%d %d %d", &a, &b, &w);
  g[a].push_back({ b, w });
  g[b].push_back({ a, w });
}

Запускаем поиск в ширину со стартовой вершины $s$.

bfs(s);

Выводим кратчайшее расстояние до вершины $d$.

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