Computer science is no more about computers
than astronomy is about telescopes.
Esta página foi inspirada em parte do capítulo 24 de CLRS. Ela trata trata do algoritmo de Dijkstra [pronuncie algo entre Dêcstra e Dêicstra], que generaliza o algoritmo Distâncias.
Veja também os verbetes Shortest path problem e Dijkstra's algorithm na Wikipedia.
Suponha que cada arco uv de um digrafo tem um peso numérico f(uv). Se P é um passeio, vamos denotar por f(P) o peso do passeio, ou seja, a soma dos pesos dos arcos do passeio. Um passeio P de um vértice r a um vértice s tem peso mínimo se
f(P) ≤ f(P′)
para todo passeio P′ de r a s. Diremos também que P é um passeio f-mínimo. A f-distância de um vértice r a um vértice s é o peso de um passeio f-mínimo de r a s.
Problema das distâncias com pesos: Dado um vértice r de um digrafo e uma função f que atribui um peso numérico a cada arco do digrafo, encontrar a f-distância de r a cada um dos demais vértices.
O problema faz sentido com quaisquer pesos reais (positivos ou negativos), mas fica muito mais difícil na presença de pesos negativos. Vamos supor, portanto, que
f(uv) ≥ 0 para cada arco uv.
Sob essa hipótese, todo passeio f-mínimo é necessariamente um caminho. (Quase! A rigor, não é bem assim, por causa dos eventuais arcos de peso nulo. Mas posso garantir que para todo passeio f-mínimo P de r a s existe um caminho C de r a s tal que f(C) = f(P).)
Se f(uv) = 1 para todo arco uv então o problema desta página é idêntico ao problema das distâncias discutido na página Distâncias. Portanto, o problema a ser discutido aqui é uma generalização daquele outro.
uv | rs | rw | wz | zs |
f(uv) | 4 | 1 | 1 | 1 |
uv | rz | zr | zs |
f(uv) | −2 | +1 | +1 |
O algoritmo descrito abaixo resolve nosso problema quando não há arcos de peso negativo. O algoritmo recebe um digrafo com vértices 1, 2, …, n e arcos definidos por listas de adjacência Adj[1..n]. Recebe também um vértice r e uma função f que atribui um peso positivo ou nulo a cada arco. O algoritmo devolve a f-distância de r a cada um dos vértices do digrafo.
Dijkstra (n, Adj, f, r) comentário: f ≥ 0 |
11 o para u ← 1 até n faça |
12 oooo dist[u] ← ∞ |
13 o dist[r] ← 0 |
14 o Q ← Cria-Fila-Vazia ( ) |
15 o para v crescendo de 1 até n faça |
16 oooo Insere-na-Fila (v, Q) |
17 o enquanto Q não está vazia faça |
18 oooo u ← Extrai-Min (Q) |
19 oooo para cada v em Adj[u] faça |
10 ooooooo se dist[u]+f(uv) < dist[v] |
11 oooooooooo então Diminui-Chave (v, Q, dist[u]+f(uv)) |
12 o devolva dist[1..n] |
(Compare com o algoritmo Distâncias.) O subalgoritmo Cria-Fila-Vazia cria uma fila de prioridades vazia; as prioridades são ditadas por dist. O comando Insere-na-Fila(v,Q) insere o vértice v na fila Q. O comando Extrai-Min retira da fila um vértice u para o qual dist[u] é mínimo. O comando Diminui-Chave(v,Q,novo) na linha 11 faz dist[v] ← novo e o que mais for preciso para restaurar a estrutura da fila de prioridades Q.
A operação no par de linhas 10-11 é conhecida como relaxação do arco uv. A ideia é óbvia: se existe um passeio de peso dist[u] de r até u então também existe um passeio de peso dist[u]+f(uv) de r até v.
Para entender por que o algoritmo funciona corretamente, é preciso entender o estado de coisas no início de cada iteração. Para simplificar a discussão, diremos que um vértice u é
No início de cada iteração do bloco de linhas 8-11 valem os seguintes invariantes:
A propriedade i afirma que
dist[x] é uma estimativa por cima
da f-distância de
r a x.
A união das propriedades i e ii garante que
se x é preto
então dist[x] é a f-distância correta
de r a x.
A propriedade iii garante que
qualquer vértice cinza que minimiza dist
está pronto para se tornar preto sem violar ii.
Dijkstra-Cinza-e-Preto (n, Adj, f, r) |
11 o para u ← 1 até n faça |
12 oooo cor[u] ← cinza |
13 oooo dist[u] ← ∞ |
14 o dist[r] ← 0 |
15 o Q ← Cria-Fila-Vazia ( ) |
16 o para v crescendo de 1 até n faça |
17 oooo Insere-na-Fila (v, Q) |
18 o enquanto Q não está vazia faça |
19 oooo u ← Extrai-Min (Q) |
10 oooo para cada v em Adj[u] faça |
11 ooooooo se cor[v] = cinza e dist[u]+f(uv) < dist[v] |
12 oooooooooo então Diminui-Chave (v, Q, dist[u]+f(uv)) |
13 oooo cor[u] ← preto |
14 o devolva dist[1..n] |
Dijkstra-Branco-Cinza-Preto (n, Adj, f, r) |
11 o para u ← 1 até n faça |
12 oooo cor[u] ← branco |
13 oooo dist[u] ← ∞ |
14 o cor[r] ← cinza |
15 o dist[r] ← 0 |
16 o Q ← Cria-Fila-Vazia ( ) |
17 o Insere-na-Fila (r, Q) |
18 o enquanto Q não está vazia faça |
19 oooo u ← Extrai-Min (Q) |
10 oooo para cada v em Adj[u] faça |
11 ooooooo se cor[v] = branco |
12 oooooooooo então cor[v] ← cinza |
13 oooooooooo então dist[v] ← dist[u]+f(uv) |
14 oooooooooo então Insere-na-Fila (v, Q) |
15 oooooooooo senão se cor[v] = cinza e dist[u]+f(uv) < dist[v] |
16 oooooooooo senão ooo então Diminui-Chave (v, Q, dist[u]+f(uv)) |
17 oooo cor[u] ← preto |
18 o devolva dist[1..n] |
O consumo de tempo do algoritmo Dijkstra depende criticamente da implementação da fila de vértices. Discutiremos duas implementações.
Suponha que a fila é simplesmente um conjunto de vértices (na prática, os elementos da fila podem ser armazenados em um vetor, em ordem arbitrária). Nesse caso, o bloco de linhas 4-6 consome tempo proporcional a n e cada execução de Extrai-Min consome tempo proporcional a n no pior caso, pois é preciso examinar todos os elementos da fila. A rotina Diminui-Chave não faz nada.
O bloco de linhas 8-11 será repetido no máximo n vezes, pois um vértice sai da fila em cada iteração e não há inserção de novos vértices na fila. Portanto, o consumo de tempo de todas as execuções da linha 8 é Ο(n²).
O consumo de tempo de cada execução do bloco de linhas 9-11 é proporcional a n no pior caso, pois cada vértice pode ter até n−1 vizinhos. Portanto, o consumo de tempo de todas as execuções do bloco de linhas 9-11 é Ο(n²). (Poderíamos reduzir essa estimativa para Ο(m), mas esse refinamento seria supérfluo para a implementação simplória que estamos estudando.)
Assim, o consumo total de tempo do algoritmo Dijkstra é
Ο(n²) .
O algoritmo não pode ser considerado
quadrático
pois o tamanho
de uma instância do problema
é n+m e não n.
Se tratarmos apenas de digrafos densos
,
em que m é da ordem de n²,
o algoritmo é linear.
A fila de prioridades pode ser estruturada como um min-heap (basta adaptar as funções que manipulam um max-heap). Nesse caso, o bloco de linhas 4-6 consome tempo proporcional a n lg n (veja construção de um heap). Cada execução da rotina Extrai-Min consome tempo constante (ou seja, independente de n). A rotina Diminui-Chave consome de tempo proporcional a lg n.
O bloco de linhas 8-11 será repetido no máximo n vezes, pois um vértice sai da fila em cada iteração e não há inserção de novos vértices na fila. Portanto, o consumo de tempo de todas as execuções da linha 8 é
Ο(n).
O número total de execuções do bloco de linhas 9-11 é limitado pelo número m de arcos. Assim, o consumo de tempo de todas as execuções do bloco de linhas 9-11 é
O consumo total de tempo do algoritmo Dijkstra é Ο(n lg n + n + m lg n) , ou seja,
Ο((n+m) lg n).
Conclusão: A menos que m seja da ordem de n², a implementação sofisticada é mais rápida que a simplória para valores grandes de n.
quebrarnem
desaparecer. Dê uma definição apropriada para a confiabilidade de um passeio. Encontre passeios de confiabilidade máxima de um vértice r a cada um dos demais vértices.
Seria muito interessante obter não só a f-distância de um vértice r a um vértice s mas também um passeio que realiza essa distância (ou seja, um passeio P de r a s que minimize f(P)). Poderíamos tratar desse assunto imediatamente, mas eu prefiro fazer isso mais tarde, depois que tiver discutido arborescências.