Algoritmos para Grafos, via Sedgewick | Índice remissivo
"Computer science is no more about computers
than astronomy is about telescopes."
—
Edsger W. Dijkstra
Esta página discute um algoritmo eficiente para o problema da SPT com custos positivos nos arcos que já foi mencionado em outra página:
Problema da SPT com Custos Positivos: Dado um vértice s de um digrafo com custos positivos nos arcos, encontrar uma SPT com raiz s no digrafo.
Um excelente algoritmo para o problema foi descoberto por Dijkstra [pronuncie algo entre "Dêcstra" e "Dêicstra"] e publicado em 1959. O algoritmo resolve uma ligeira generalização do problema: ele aceita quaisquer custos não negativos (ou seja, admite arcos de custo positivo ou nulo).
[Esta página é um resumo das seções 21.1 (Underlying Principles) e 21.2 (Dijkstra's Algorithm), p.273-290 do livro de Sedgewick.]
O exemplo [copiado de 'Algorithms', 4th.ed., de Sedgewick e Wayne] mostra uma SPT com raiz 5 num digrafo com custos nos arcos.
4-5 .35
5-4 .36
4-7 .37
5-7 .28
7-5 .28
5-1 .32
0-4 .38
0-2 .26
7-3 .39
1-3 .29
2-7 .34
6-2 .40
3-6 .52
6-0 .58
6-4 .93
Cada iteração do algoritmo de Dijkstra começa com uma arborescência T com raiz s. Para dizer o que acontece durante a iteração, precisamos dos seguintes conceitos. A franja de T é o conjunto de todos os arcos que saem de T. (Compare com o conceito de corte.) O preço de um vértice w que esteja fora de T é
a distância de s a w no digrafo T + F,
sendo F a franja de T. Em outras palavras, o preço de w é o custo de um caminho de s a w que é mínimo no digrafo T + F. O último arco do caminho está necessariamente na franja F e será chamado arco-franja de w.
No começo da primeira iteração, a arborescência T consiste no vértice s e nada mais. Cada iteração do algoritmo consiste no seguinte:
(Pode-se dizer, informalmente, que o algoritmo escolhe sempre um vértice w0 fora de T que é o "mais próximo" de T.) No início da última iteração, para cada vértice v, a distância de s a v em T é também a distância de s a v no digrafo e portanto T é uma SPT.
Nas implementações abaixo, a arborescência T será representada por um vetor de pais parent; os preços dos vértices serão armazenados num vetor dist; e as pontas iniciais dos arcos-franja serão armazenadas num vetor frj. (O nome do vetor de preços, dist, é apropriado porque o preço de um vértice é uma distância num subdigrafo do nosso digrafo.)
Aplique o algoritmo de Dijkstra ao digrafo com custos nos arcos definido a seguir para encontrar uma SPT com raiz 0.
0-1 0-2 1-3 1-4 2-3 2-4 3-5 4-5 6-5
.1 .2 .8 .9 .6 .7 .1 .9 .0
Registramos a seguir o estado dos vetores parent, frj e dist no início de cada iteração, com "-" indicando valores indefinidos e "*" indicando ∞.
parent franja dist
0 1 2 3 4 5 6 0 1 2 3 4 5 6
0 - - - - - - 0-1 0-2 .0 .1 .2 * * * *
0 0 - - - - - 1-3 1-4 0-2 .0 .1 .2 .9 1.0 * *
0 0 0 - - - - 1-3 1-4 2-3 2-4 .0 .1 .2 .8 .9 * *
0 0 0 2 - - - 1-4 2-4 3-5 .0 .1 .2 .8 .9 .9 *
0 0 0 2 - 3 - 1-4 2-4 .0 .1 .2 .8 .9 .9 *
0 0 0 2 2 3 - .0 .1 .2 .8 .9 .9 *
0-1 0-5 1-2 1-3 2-5 2-6 3-6 5-1 5-4 5-6 6-3 6-4
.1 .6 .1 .2 .5 .5 .5 .1 .0 .3 .2 .2
Seja T a arborescência com raiz 0 cujos arcos são 0-1 1-2 1-3. Seja F a franja de T. Faça uma lista dos arcos de F. Dê todos os caminhos mínimos em T + F que começam em 0.
0-1 0-4 1-5 2-0 2-3 2-4 4-3 5-0 5-2
.1 .3 .1 .1 .6 .5 .1 .4 .2
6-1 6-2 1-2 3-4 3-5 3-0 4-1 4-2 4-0 5-1 6-0 0-1 0-2
1.5 1.6 2.5 2.5 1.5 1.5 4.4 4.2 1.1 4.5 4.7 3.0 3.0
Suponha que nosso digrafo está representado por sua matriz de adjacência. Assim, se v-w não é arco então adj[v][w] vale maxCOST, que nesse caso tem o sabor de infinito. Supõe-se que o valor de maxCOST é tão grande que não se confunde com o custo de um caminho simples. Em virtude dessa representação, o digrafo é completo e a franja no começo da primeira iteração tem um arco s-w para cada vértice w.
/* Recebe digrafo G com custos não negativos nos arcos e um vértice s. Calcula uma SPT com raiz s. A SPT é armazenada no vetor parent. As distâncias a partir de s são armazenadas no vetor dist. */
/* A função supõe que maxCOST é estritamente maior que a soma dos custos de todas os arcos. Supõe também que o digrafo tem no máximo maxV vértices. (O código abaixo é uma versão modificada do Programa 20.3, p.238, de Sedgewick.) */
void DIGRAPHsptD1( Digraph G, Vertex s, Vertex parent[], double dist[]) { Vertex w, w0, frj[maxV]; for (w = 0; w < G->V; w++) { parent[w] = -1; dist[w] = G->adj[s][w]; frj[w] = s; } parent[s] = s; dist[s] = 0.0; while (1) { double mindist = maxCOST; for (w = 0; w < G->V; w++) if (parent[w] == -1 && mindist > dist[w]) mindist = dist[w0=w]; if (mindist == maxCOST) break; parent[w0] = frj[w0]; for (w = 0; w < G->V; w++) if (dist[w] > dist[w0] + G->adj[w0][w]) { dist[w] = dist[w0] + G->adj[w0][w]; frj[w] = w0; } } }
(Três observações técnicas sobre o código: 1. Note como a comparação de dist[w] com dist[w0] + G->adj[w0][w] trata corretamente do caso em que w0 e w não são adjacentes e portanto G->adj[w0][w] vale maxCOST. 2. Estamos supondo, implicitamente, que maxCOST é menor que a metade de DBL_MAX, de modo que a expressão dist[w0] + G->adj[w0][w] não produz overflow. 3. Embora a variável w0 não seja explicitamente inicializada, seu valor está bem definido sempre que ela é usada.)
No começo de cada iteração, valem os seguintes invariantes:
No fim da execução do algoritmo, em virtude dos invariantes 2 e 3, dist é um potencial. Também pelo invariante 3, se existe caminho de s a algum vértice v então dist[v] é menor que maxCOST. Segue daí que a função DIGRAPHsptD1 está correta.
A operação mais característica do algoritmo é a relaxação do arco w0-w:
if (dist[w] > dist[w0] + G->adj[w0][w])
dist[w] = dist[w0] + G->adj[w0][w];
Essa operação aparece em toda implementação do algoritmo.
Considere o digrafo com custos nos arcos definido a seguir [copiado das transparências de José Coelho de Pina, 2011]. Use o algoritmo de Dijkstra para encontrar uma SPT com raiz 0.
0-2 0-3 0-4 2-4 3-4 3-5 4-1 4-5 5-1 1-2
.7 .2 .4 .1 .1 .3 .4 .1 .2 .0
Registramos a seguir o estado dos vetores parent, frj e dist no início de cada iteração, com "-" indicando valores indefinidos e "*" indicando ausência de arco (e portanto custo ∞):
parent frj dist
0 1 2 3 4 5 0 1 2 3 4 5 0 1 2 3 4 5
0 - - - - - - - 0 0 0 - .0 * .7 .2 .4 *
0 - - 0 - - - - 0 0 3 3 .0 * .7 .2 .3 .5
0 - - 0 3 - - 4 0 0 3 4 .0 .7 .7 .2 .3 .4
0 - - 0 3 4 - 5 0 0 3 4 .0 .6 .7 .2 .3 .4
0 5 - 0 3 4 - 5 1 0 3 4 .0 .6 .6 .2 .3 .4
0 5 1 0 3 4 - 5 1 0 3 4 .0 .6 .6 .2 .3 .4
A função DIGRAPHsptD1 consome tempo proporcional a V 2 no pior caso, sendo V o número de vértices de G. Portanto, a função é linear quando restrita a digrafos densos. Também é linear quando restrita a digrafos representados por matriz de adjacência.
(O desempenho da função DAGmin, que resolve o problema em DAGs, é bem melhor.)
0-2 0-3 0-4 2-4 3-4 3-5 4-1 4-5 5-1 1-2
.7 .5 .3 .1 .1 .2 .0 .3 .5 .3
vértice 0 1 2 3 4 5
coordenadas (1,3) (2,1) (6,5) (3,4) (3,7) (5,3)
Suponha que as arestas do grafo são 1-0 3-5 5-2 3-4 5-1 0-3 0-4 4-2 2-3 e o custo de cada aresta é igual ao comprimento do segmento de reta que liga as pontas da aresta. Submeta o grafo à função DIGRAPHsptD1 com s = 0. Exiba o estado dos vetores parent e dist no início de cada iteração.
void DIGRAPHsptD1( Digraph G, Vertex s, Vertex parent[], double dist[]) {
Vertex w, w0, frj[maxV];
for (w = 0; w < G->V; w++) {
parent[w] = -1;
dist[w] = maxCOST;
}
frj[s] = s;
dist[s] = 0.0;
while (1) {
double mindist = maxCOST;
for (w = 0; w < G->V; w++) {
if (parent[w] == -1 && mindist > dist[w])
mindist = dist[w0=w];
if (mindist == maxCOST) break;
parent[w0] = frj[w0];
for (w = 0; w < G->V; w++)
if (dist[w] > dist[w0] + G->adj[w0][w]) {
dist[w] = dist[w0] + G->adj[w0][w];
frj[w] = w0;
}
}
}
A seguinte implementação do algoritmo de Dijkstra é adequada para digrafos esparsos. Assim, é apropriado supor que o digrafo é representado por listas de adjacência:
/* Recebe digrafo G com custos não negativos nos arcos e um vértice s. Calcula uma SPT com origem s. A SPT é armazenada no vetor parent. As distâncias a partir de s são armazenadas no vetor dist. */
/* A implementação supõe que a soma dos custos de todos os arcos é estritamente menor que maxCOST. Supõe também que o digrafo tem no máximo maxV vértices. (O código abaixo é uma versão modificada dos Programas 20.4, p.242, e 21.1, p.284, de Sedgewick.) */
void DIGRAPHsptD2( Digraph G, Vertex s, Vertex parent[], double dist[]) { link p; Vertex w, w0, frj[maxV]; PQinit( ); for (w = 0; w < G->V; w++) parent[w] = frj[w] = -1; parent[s] = s; dist[s] = 0.0; for (p = G->adj[s]; p != NULL; p = p->next) { dist[p->w] = p->cost; PQinsert( p->w); frj[p->w] = s; } while (!PQempty( )) { w0 = PQdelmin( ); parent[w0] = frj[w0]; for (p = G->adj[w0]; p != NULL; p = p->next) { if (frj[p->w] == -1) { dist[p->w] = dist[w0] + p->cost; PQinsert( p->w); frj[p->w] = w0; } else if (dist[p->w] > dist[w0] + p->cost) { dist[p->w] = dist[w0] + p->cost; PQdec( p->w); frj[p->w] = w0; } } } }
A função DIGRAPHsptD2 usa uma fila de prioridades (= priority queue) para escolher, eficientemente, o próximo vértice a ser acrescentado à SPT. [Veja capítulo 9 (Priority Queues and Heapsort), p.389, do volume 1 do livro de Sedgewick.] Trata-se de uma fila de vértices com prioridades definidas pelo vetor dist. A fila é manipulada pelas seguintes funções:
A implementação clássica da fila de prioridades usa uma estrutura de heap.
Rastreamento do algoritmo de Dijkstra
aplicado ao digrafo do exemplo A acima,
com raiz 0.
O vetor distTo da figura
corresponde ao nosso dist.
O vetor edgeTo da figura
corresponde aproximadamente ao nosso parent.
A cor vermelha identifica a franja da arborescência
(que é indicada em preto).
[Copiado de 'Algorithms', 4th.ed., de Sedgewick e Wayne.]
Se a fila de prioridades for implementada como um heap então DIGRAPHsptD2 consome tempo proporcional a (V+A) log V no pior caso, sendo V o número de vértices e A o número de arcos de G. (Se G for fracamente conexo então A ≥ V−1 e portanto o consumo de tempo é proporcional a A log V no pior caso.)
Se nos restringirmos a digrafos esparsos, DIGRAPHsptD2 é assintoticamente mais rápida que DIGRAPHsptD1. Mas se G é denso então DIGRAPHsptD1 é mais rápida.
(O desempenho da função DAGmin, que resolve o problema em DAGs, é bem melhor.)
Podemos reorganizar o código de DIGRAPHsptD2 de modo a inserir todos os vértices na fila de prioridades antes mesmo do início do processo iterativo:
/* (Código inspirado no Programa 21.1, p.284, de Sedgewick.) */
void DIGRAPHsptD3( Digraph G, Vertex s, Vertex parent[], double dist[]) { Vertex w, w0; link p; for (w = 0; w < G->V; w++) { parent[w] = -1; dist[w] = maxCOST; } parent[s] = s; dist[s] = 0.0; for (p = G->adj[s]; p != NULL; p = p->next) dist[p->w] = p->cost; PQinit( ); for (w = 0; w < G->V; w++) if (w != s) PQinsert( w); while (!PQempty( )) { w0 = PQdelmin( ); if (dist[w0] == maxCOST) break; for (p = G->adj[w0]; p != NULL; p = p->next) { if (dist[p->w] > dist[w0] + p->cost) { dist[p->w] = dist[w0] + p->cost; PQdec( p->w); parent[p->w] = w0; } } } }
