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.