Розбір

$0-1$ Breadth-First Search (or $0-1$ BFS) is a modification of the classic Breadth-First Search (BFS) algorithm, used for finding shortest paths in graphs. The key difference of this algorithm is that the edge weights in the graph can only be $0$ or $1$, allowing for a significant optimization in search efficiency.

Problem Statement. Imagine we have a weighted graph where the edge weights are either $0$ or $1$. For example, such a graph can represent a city where certain roads are free (weight $0$), while others have a toll (weight $1$). Our goal is to find the shortest path from one vertex to another, taking these weights into account.

Limitations of the Standard Breadth-First Search Algorithm. The classic BFS algorithm has a complexity of $O(V+E)$ and is used to find shortest paths in unweighted graphs, but it only works effectively when all edges have the same weight. If edge weights vary, this approach becomes inefficient. Typically, Dijkstra's algorithm is used for weighted graphs, with a complexity of $O(V^2+E)$ or $O(E\cdot lo{g}_{2}V)$. However, for graphs with edge weights of only $0$ and $1$, there is a faster approach — $0-1$ BFS.

0-1 BFS Algorithm

In $0-1$ BFS, we use a double-ended queue (deque). The idea is as follows:

1. 1. We start from the initial vertex $start$ and add it to the deque with an initial distance of $0$.

2. 2. When processing each vertex $u$ (which is dequeued from the front), we examine its neighbors $v$:

   • If the edge $(u,v)$ has a weight of $0$, the neighboring vertex $v$ is added to the front of the deque with the current distance $(dist[v]=dist[u])$.

   • If the edge $(u,v)$ has a weight of $1$, the neighboring vertex $v$ is added to the back of the deque with an increased distance of one $(dist[v]=dist[u]+1)$.

3. This ensures an efficient order of vertex processing: vertices reachable through edges with smaller weights are processed earlier.

Thus, the use of a double-ended queue guarantees that we always have access to the vertex with the minimum distance at the front of the deque, and the algorithm’s complexity remains $O(V+E)$.

Edge relaxation in $0-1$ BFS is similar to the classical relaxation in Dijkstra’s algorithm but differs in that it uses a deque instead of a priority queue to order vertices based on edge weights.

Let's consider the following example. Initialize the array of shortest distances $dist$ and the queue $q$:

Examine the edges originating from vertex $1$ and relax the edges $(1,2)$ and $(1,3)$. Vertex $3$ will be added to the front of the queue, while vertex $2$ will be added to the back of the queue.

However, the value $dist[2]=1$ is not final. Traverse edge $3-4$ and set $dist[4]=0$, making the queue $q=(4,2)$. Then, examine edge $4-2$, and the value $dist[2]$ is updated to $0$. Thus, $dist[2]$ took on two different values as a result of relaxation (first $1$, then $0$).

Example

The graph given in the example looks as follows:

The length of the shortest path from vertex $1$ to vertex $3$ is $1$, and the shortest path is as follows: $1-2-3$.

Algorithm realization

Declare the constant infinity.

#define INF 0x3F3F3F3F

Declare the array of shortest distances $dist$ and the adjacency list of the graph $g$.

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

The bfs function implements breadth-first search from the vertex $start$.

void bfs(int start)
{

Initialize the array of shortest distances $dist$.

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

Declare a queue and enqueue the starting vertex $start$.

  deque<int> q;
  q.push_back(start);

Continue the breadth-first search algorithm while the queue is not empty.

  while (!q.empty())
  {

Extract the vertex $v$ from the front of the queue.

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

Iterate through the edges outgoing from vertex $v$.

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

The current edge $(v,to)$ has a weight $w$. Perform its relaxation.

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

If the edge is relaxed, recalculate the shortest distance $dist[to]$.

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

Depending on the weight of the edge $w$, add vertex $to$ to the end or the front of the queue.

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

The main part of the program. Read the input data.

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

Read the graph.

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 });
}

Start the breadth-first search from the starting vertex $s$.

bfs(s);

Print the shortest distance to vertex $d$.

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