A distância de s a t é 6.
[Copiado das transparências 2006 de Sedgewick.]
Algoritmos para Grafos, via Sedgewick | Índice remissivo
Qual o caminho mais curto do bairro de Pinheiros ao bairro de Itaquera na cidade de São Paulo?
[Esta página corresponde aproximadamente à seção 18.7 (Breadth-First Search), p.114-124, do capítulo 18 do livro de Sedgewick.]
Um caminho C num digrafo é mínimo se não existe outro caminho com mesma origem e mesmo término que C mas comprimento menor que o de C. É claro que todo caminho mínimo é simples.
A distância de um vértice s a um vértice t num digrafo é o comprimento de um caminho mínimo de s a t. Se não existe caminho algum de s a t, a distância de s a t é infinita. A distância de s a t é d se e somente se (1) existe um caminho de comprimento d de s a t e (2) nenhum caminho de s a t tem comprimento menor que d.
Em geral, a distância de um vértice s a um vértice t é diferente da distância de t a s. Num grafo, entretanto, as duas distâncias são iguais.
Nosso problema básico é determinar a distância de um vértice a outro:
Problema: Dados vértices s e t de um digrafo G, determinar a distância de s a t.
A seguinte generalização do problema não é mais difícil que o original: Dado s, calcular a distância de s a cada um dos demais vértices de G.
Qual a distância do vértice noroeste ao vértice sudeste?
Seja G o digrafo com 6 vértices definido pelos arcos listados a seguir.
0-2 0-3 0-4 1-2 1-4 2-4 3-4 3-5 4-5 5-1
Segue a tabela de distâncias do vértice 0 a cada um dos demais vértices:
v 0 1 2 3 4 5
distância de 0 a v 0 3 1 1 1 2
#define INFINITO G->V
static int dist[maxV];
void distancias( Graph G, Vertex s) {
Vertex v;
for (v = 0; v < G->V; v++) dist[v] = INFINITO;
dist[s] = 0;
dfsR( G, s);
}
void dfsR( Graph G, Vertex v) {
link p;
for (p = G->adj[v]; p != NULL; p = p->next)
if (dist[p->w] == INFINITO) {
dist[p->w] = dist[v] + 1;
dfsR( G, p->w);
}
}
#define INFINITO G->V
static int dist[maxV];
void distancias( Digraph G, Vertex s) {
int d;
Vertex v, w;
for (v = 0; v < G->V; v++) dist[v] = INFINITO;
dist[s] = 0;
for (d = 0; d < G->V; d++)
for (v = 0; v < G->V; v++)
if (dist[v] == d)
for (w = 0; w < G->V; w++)
if (G->adj[v][w] == 1 && dist[w] == INFINITO)
dist[w] = d + 1;
}
A busca em largura é o método perfeito para calcular distâncias a partir de um dado vértice s. Ele visita todos os vértices que estão à distância 1 de s, depois todos os vértices que estão à distância 2 de s, e assim por diante.
static int dist[maxV];/* Armazena no vetor dist a distância do vértice s a cada um dos demais vértices do digrafo G: para cada vértice v, dist[v] é a distância de s a v. (Código inspirado no programa 18.9, p.119, de Sedgewick.) */
void DIGRAPHdist( Digraph G, Vertex s) { const int INFINITO = G->V; Vertex v, w; for (v = 0; v < G->V; v++) dist[v] = INFINITO; QUEUEinit( G->V); dist[s] = 0; QUEUEput( s); while (!QUEUEempty( )) { v = QUEUEget( ); for (w = 0; w < G->V; w++) if (G->adj[v][w] == 1 && dist[w] == INFINITO) { dist[w] = dist[v] + 1; QUEUEput( w); } } QUEUEfree( ); }
(Nesse código, representamos o infinito por G->V. Isso faz perfeito sentido pois nenhum caminho tem comprimento ≥ G->V.) Para entender o algoritmo e provar que a função DIGRAPHdist está correta é preciso observar os seguintes invariantes: no início de cada iteração do while,
Prova dos invariantes: No início da primeira iteração, essas propriedades são obviamente válidas. Suponha agora que elas valem no início de uma iteração qualquer em que a fila não está vazia e seja v o primeiro vértice da fila. Vamos mostrar que as propriedades continuam válidas no início da próxima iteração:
No fim do processo iterativo, a fila está vazia e portanto, em virtude do invariante 3, o vetor dist é um potencial, ou seja,
dist[y] - dist[x] ≤ 1 para cada arco x-y de G.
(Imagine que dist[x] é a altura de x acima do solo. É claro que s está à altura 0. A desigualdade acima diz que nenhum arco sobe mais que uma unidade.) Segue daí que para qualquer caminho P que vai de s a um vértice t tem-se dist[t]-dist[s] ≤ |P|, sendo |P| o comprimento de P. Como dist[s] é 0, temos
dist[t] ≤ |P|.
Em outras palavras, para todo vértice t, não existe caminho de s a t que seja mais curto de dist[t]. Por outro lado, é fácil verificar (veja a arborescência da busca abaixo) que no fim da execução do algoritmo, para cada vértice t, existe um caminho que vai de s a t e tem comprimento dist[t] (a menos que dist[t] seja INFINITO). Logo, dist[t] é, de fato, a distância de s a t.
Considere o grafo (ou seja, digrafo simétrico) definido pelo conjunto de arestas abaixo. (Trata-se do mesmo exemplo que examinamos na página de busca em largura.) Represente o grafo por sua matriz de adjacência.
0-2 2-6 6-4 4-5 5-0 0-7 7-1 7-4 3-4 3-5
Agora use a função DIGRAPHdist para calcular as distâncias a partir do vértice 0. Eis o estado do vetor dist no início de sucessivas iterações (com "-" no lugar de "INFINITO"):
0 1 2 3 4 5 6 7
0 - - - - - - -
0 - 1 - - 1 - 1
0 - 1 - - 1 2 1
0 - 1 2 2 1 2 1
0 2 1 2 2 1 2 1
Quanto tempo a função DIGRAPHdist consome quando aplicada a um digrafo com V vértices e A arcos? A função consome tempo proporcional a V2 no pior caso. Portanto, a função é linear quando aplicada a digrafos densos.
A variante da função que usa listas de adjacência consome tempo proporcional a V+A no pior caso, e portanto é linear para todos os digrafos.
#define INFINITO G->V
static int dist[maxV];
void distance( Graph G, Vertex s) {
Vertex v, w;
int conta = 0;
for (v = 0; v < G->V; v++) dist[v] = INFINITO;
QUEUEinit( G->V);
dist[s] = 0;
QUEUEput( s);
while (!QUEUEempty( )) {
v = QUEUEget( );
for (w = 0; w < G->V; w++)
if (G->adj[v][w] == 1 && dist[w] == INFINITO) {
dist[w] = conta;
QUEUEput( w);
}
conta++;
}
}
Se acrescentar ao código de DIGRAPHdist o cálculo de um vetor de pais parent, teremos uma representação da arborescência de busca em largura. É claro que para cada arco v-w da arborescência tem-se dist[w]-dist[v] = 1.
Essa arborescência pode ser chamada arborescência das distâncias pois, para cada vértice t, o único caminho de s a t na arborescência é um caminho mínimo no digrafo (a não ser, é claro, que dist[t] seja INFINITO).
O fragmento de código abaixo imprime o inverso do caminho de s a t na arborescência:
for (v = t; v != s; v = parent[v])
printf( "%d-", v)
printf( "%d\n", s)
8-9 3-7 1-4 7-8 0-5 5-2 3-8 2-9 0-6 4-9 2-6 6-4
Calcule a distância do vértice 0 a cada um dos demais vértices. Faça um desenho da arborescência de distâncias. Repita o exercício supondo que o grafo é representado por listas de adjacência construídas inserindo as arestas, na ordem dada, num grafo inicialmente vazio.
Resposta: A expressão "distância entre s e t" parece sugerir que as distâncias de s a t e de t a s são iguais. No entanto, a distância de s a t é, em geral, diferente da distância de t a s. (Em grafos, entretanto, as duas distâncias são de fato iguais.)
Resposta: Toda distância é minima por definição. Dizer "distância mínima" ou "a menor distância" é uma redundância sem sentido.
Resposta: Não é uma boa ideia porque INT_MAX não tem qualquer relação com o tamanho do grafo que estamos processando. Em particular, não há qualquer relação entre INT_MAX e o número G->V de vértices do grafo. Na função DIGRAPHdist, por exemplo, é muito melhor representar o infinito por G->V.
