Ricerca in ampiezza 0-1#10056

Ricerca in ampiezza 0-1 (Editoriale)

$0 - 1$ 0 - 1 ricerca in ampiezza (o $0 - 1$ 0 - 1 BFS) — è una modifica dell'algoritmo classico di ricerca in ampiezza (BFS), utilizzato per trovare i cammini più brevi nei grafi. La differenza di questo algoritmo consiste nel fatto che i pesi degli archi del grafo possono assumere esclusivamente i valori $0$ oppure $1$ , il che permette di ottimizzare significativamente la ricerca.

Postazione del problema. Immaginiamo di avere un grafo pesato, in cui i pesi degli archi sono $0$ oppure $1$ . Ad esempio, un grafo del genere si può incontrare quando lavoriamo con una città in cui alcune strade sono gratuite (peso $0$ ), mentre per altre bisogna pagare (peso $1$ ). Vogliamo trovare il cammino più breve da un vertice del grafo a un altro tenendo conto di questi pesi.

Il problema dell'algoritmo standard di ricerca in ampiezza. L'algoritmo classico di ricerca in ampiezza (BFS) ha una complessità di $O (V + E)$ O(V + E) e viene utilizzato per trovare i cammini più brevi in un grafo, ma è adatto solo per grafi in cui tutti gli archi hanno lo stesso peso. Nel caso in cui i pesi degli archi siano diversi, tale approccio risulta già inefficiente — a tale scopo si utilizza solitamente l'algoritmo di Dijkstra con complessità $O (V^{2} + E)$ O(V^2 + E) oppure $O (E \cdot l o g_{2} V)$ O(E \cdot log_2V). Ma per i grafi con pesi solo $0$ e $1$ esiste un approccio più veloce — $0 - 1$ 0 - 1 BFS.

Algoritmo 0-1 BFS

Nel $0 - 1$ 0 - 1 BFS utilizziamo una coda a doppia estremità (deque). L'idea è la seguente:

Partiamo dal vertice sorgente $s t a r t$ e lo aggiungiamo alla coda con distanza iniziale pari a $0$ .
Durante l'elaborazione di ciascun vertice $u$ (che viene estratto dalla testa della coda), esaminiamo i suoi vicini $v$ :
- Se l'arco $(u, v)$ ha peso $0$ , allora il vertice adiacente $v$ viene inserito all'inizio della coda con la distanza corrente $(d i s t [v] = d i s t [u])$ (dist[v] = dist[u]).
- Se l'arco $(u, v)$ ha peso $1$ , allora il vertice adiacente $v$ viene inserito alla fine della coda con l'incremento della distanza di un'unità $(d i s t [v] = d i s t [u] + 1)$ (dist[v] = dist[u] + 1).
Ciò consente di mantenere in modo efficiente l'ordine corretto di elaborazione dei vertici: i vertici raggiungibili tramite archi con peso minore vengono elaborati prima.

Così, l'utilizzo di una coda a doppia estremità garantisce che abbiamo sempre accesso al vertice con distanza minima all'inizio della coda, e la complessità di funzionamento dell'algoritmo rimane $O (V + E)$ O(V + E).

Il rilassamento degli archi nella ricerca in ampiezza $0 - 1$ 0 - 1 è simile al classico rilassamento nell'algoritmo di Dijkstra, ma si differenzia per l'uso di una coda a doppia estremità (deque) invece di una coda con priorità (priority queue) per ordinare i vertici in base al peso degli archi.

L'algoritmo $0 - 1$ 0-1 BFS (a differenza del classico BFS) non garantisce che ogni vertice venga visitato con la distanza minima già la prima volta, specialmente se lo stesso vertice può essere raggiunto tramite più percorsi. Pertanto il rilassamento degli archi è obbligatorio.

Consideriamo il seguente esempio. Inizializziamo l'array delle distanze minime $d i s t$ e la coda $q$ :

Consideriamo gli archi uscenti dal vertice $1$ . Rilassiamo gli archi $(1, 2)$ e $(1, 3)$ . Il vertice $3$ verrà inserito all'inizio della coda, mentre il vertice $2$ alla fine della coda.

Tuttavia il valore $d i s t [2] = 1$ dist[2] = 1 non è definitivo. Percorriamo l'arco $3 - 4$ 3 - 4 e impostiamo $d i s t [4] = 0$ dist[4] = 0, $q u e u e = (4, 2)$ queue = (4, 2). Poi consideriamo l'arco $4 - 2$ 4 - 2 e il valore $d i s t [2]$ verrà impostato a $0$ . Così, $d i s t [2]$ ha assunto due valori diversi come risultato del rilassamento (prima $1$ , poi $0$ ).

Esempio

Il grafo riportato nell'esempio ha la forma:

La lunghezza del cammino più breve dal vertice $1$ al vertice $3$ è pari a $1$ , e il cammino più breve stesso ha la forma: $1 - 2 - 3$ 1 - 2 - 3.

Implementazione dell'algoritmo

Dichiariamo la costante infinito.

#define INF 0x3F3F3F3F

Dichiariamo l'array delle distanze minime $d i s t$ e la lista di adiacenza del grafo $g$ .

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

La funzione bfs implementa la ricerca in ampiezza a partire dal vertice $s t a r t$ .

void bfs(int start)
{

Inizializziamo l'array delle distanze minime $d i s t$ .

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

Dichiariamo la coda e inseriamo in essa il vertice iniziale $s t a r t$ .

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

Continuiamo l'algoritmo di ricerca in ampiezza finché la coda non è vuota.

  while (!q.empty())
  {

Estraiamo dalla testa della coda il vertice $v$ .

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

Scorriamo gli archi uscenti dal vertice $v$ .

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

L'arco corrente $(v, t o)$ (v, to) ha peso $w$ . Eseguiamo il suo rilassamento.

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

Se l'arco si rilassa, allora ricalcoliamo la distanza minima $d i s t [t o]$ dist[to].

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

A seconda del peso dell'arco $w$ , aggiungiamo il vertice $t o$ alla fine o all'inizio della coda.

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

C++

Parte principale del programma. Leggiamo i dati di input.

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

Leggiamo il grafo.

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

Avviamo la ricerca in ampiezza a partire dal vertice iniziale $s$ .

bfs(s);

Stampiamo la distanza minima fino al vertice $d$ .

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