Distância
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.
Busca em largura e distâncias
O algoritmo de busca em largura foi concebido sob medida para calcular distâncias a partir de um 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.
No início de cada iteração, a fila consiste em
1. zero ou mais vértices à distância d de s,
2. seguidos de zero ou mais vértices à distância d+1 de s,
para algum d. Essa propriedade permite concluir que, no início de cada iteração, para todo vértice x, se dist[x] é diferente de -1 então dist[x] é a distância de s a x.
Exemplo
Considere o grafo (digrafo simétrico) definido pelo conjunto de arestas abaixo.
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 distDigrafo 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 "-1"):
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
Caminhos mínimos e arborescência de distâncias
Se acrescentar ao código de distDigrafo o cálculo de um vetor de pais pai, teremos uma representação da arborescência de busca em largura.
No presente contexto, essa árvore pode ser chamada arborescência das distâncias: para cada vértice x tal que dist[x] é diferente de -1, o único caminho de s a x na arborescência é um caminho mínimo no digrafo. O fragmento de código abaixo imprime o inverso desse caminho:
Desempenho
A função distDigrafo é linear: ela consome tempo proporcional a V2 no pior caso. A variante dessa função para listas de adjacência consome tempo proporcional a V+E.
A versão de distDigrafo que calcula a arborescência de distâncias também é linear.
Digrafos com custos nos arcos
Muitas aplicações associam um número a cada arco de um digrafo. Diremos que esse número é o custo da arco. Vamos supor, em geral, que esses números são do tipo double, podendo ser positivos, negativos, ou nulos. Essa associação de custos aos arcos pode ser entendida como uma função que leva o conjunto de arcos num conjunto de números.
Dependendo da aplicação, pode ser mais apropriado dizer "peso" ou "comprimento" no lugar de "custo". [Sedgewick diz weight no lugar do nosso "custo". Mas isso aumenta o número de variáveis cujo nome começa "w", o que torna os programas menos legíveis.]
Grafos com custos nas arestas
Grafos com custos nas arestas têm uma peculiaridade previsível: os dois arcos que constituem cada aresta têm o mesmo custo. O custo de uma aresta, nesse caso, é o custo de qualquer dos dois arcos que constituem a aresta.
Exercícios para Fixação
1. O código distDigrafo utiliza matriz ou lista de adjacências para representar o grafo? Implemente o mesmo código para o outro tipo de representação.
2. Como ficaria esse código com o cálculo do vetor de pais?
3. Qual é o resultado de trocarmos a bfs por dfs neste código?
Fonte: IME
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.
Busca em largura e distâncias
O algoritmo de busca em largura foi concebido sob medida para calcular distâncias a partir de um 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.
int dist[maxV];
/* A função distDigrafo armazena no vetor dist a distância do vértice s a cada um dos demais vértices do digrafo G: dist[v] é a distância de s a v. Distância infinita é representada por -1.*/
void distDigrafo (int s) {
int v, w;
int ini,fim;
for (v = 0; v < n; v++) dist[v] = -1;
ini = fim = 0;
dist[s] = 0;
fila[ini++] = s;
while (ini > fim) {
v = fila[fim++];
for (w = 0; w < n; w++)
if (g[v][w] == 1)
if (dist[w] == -1) {
dist[w] = dist[v] + 1;
fila[ini++] = w;
}
}
}
No início de cada iteração, a fila consiste em
1. zero ou mais vértices à distância d de s,
2. seguidos de zero ou mais vértices à distância d+1 de s,
para algum d. Essa propriedade permite concluir que, no início de cada iteração, para todo vértice x, se dist[x] é diferente de -1 então dist[x] é a distância de s a x.
Exemplo
Considere o grafo (digrafo simétrico) definido pelo conjunto de arestas abaixo.
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 distDigrafo 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 "-1"):
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
Caminhos mínimos e arborescência de distâncias
Se acrescentar ao código de distDigrafo o cálculo de um vetor de pais pai, teremos uma representação da arborescência de busca em largura.
No presente contexto, essa árvore pode ser chamada arborescência das distâncias: para cada vértice x tal que dist[x] é diferente de -1, o único caminho de s a x na arborescência é um caminho mínimo no digrafo. O fragmento de código abaixo imprime o inverso desse caminho:
for (v = x; v != s; v = pai[v])
printf("%d-", v)
printf("%d\n", s)
Desempenho
A função distDigrafo é linear: ela consome tempo proporcional a V2 no pior caso. A variante dessa função para listas de adjacência consome tempo proporcional a V+E.
A versão de distDigrafo que calcula a arborescência de distâncias também é linear.
Digrafos com custos nos arcos
Muitas aplicações associam um número a cada arco de um digrafo. Diremos que esse número é o custo da arco. Vamos supor, em geral, que esses números são do tipo double, podendo ser positivos, negativos, ou nulos. Essa associação de custos aos arcos pode ser entendida como uma função que leva o conjunto de arcos num conjunto de números.
Dependendo da aplicação, pode ser mais apropriado dizer "peso" ou "comprimento" no lugar de "custo". [Sedgewick diz weight no lugar do nosso "custo". Mas isso aumenta o número de variáveis cujo nome começa "w", o que torna os programas menos legíveis.]
Grafos com custos nas arestas
Grafos com custos nas arestas têm uma peculiaridade previsível: os dois arcos que constituem cada aresta têm o mesmo custo. O custo de uma aresta, nesse caso, é o custo de qualquer dos dois arcos que constituem a aresta.
Exercícios para Fixação
1. O código distDigrafo utiliza matriz ou lista de adjacências para representar o grafo? Implemente o mesmo código para o outro tipo de representação.
2. Como ficaria esse código com o cálculo do vetor de pais?
3. Qual é o resultado de trocarmos a bfs por dfs neste código?
Fonte: IME
