Introdução a rede de computadores

Profº: Leandro Teófilo

Aluno: Brehme Augusto Dias Resende

Algoritmo de Dijkstra
O algoritmo de Dijkstra é o mais famoso dos algoritmos para cálculo de caminho de custo
mínimo entre vértices de um grafo e, na prática, o mais empregado.

Escolhido um vértice como raiz da busca, este algoritmo calcula o custo mínimo deste vértice
para todos os demais vértices do grafo. O algoritmo pode ser usado sobre grafos orientados
(dígrafos), ou não, e admite que todas as arestas possuem pesos não negativos (nulo é possível).
Esta restrição é perfeitamente possível no contexto de redes de transportes, onde as arestas
representam normalmente distâncias ou tempos médios de percurso; poderão existir, no entanto,
aplicações onde as arestas apresentam pesos negativos, nestes casos o algoritmo não funcionará
corretamente.

Funcionamento do algoritmo

Assumiremos um conjunto, chama-lo-emos PERM, que contém inicialmente apenas o

vértice fonte (raiz da busca) s. A qualquer momento PERM contém todos os vértices
para os quais já foram determinados os menores caminhos usando apenas vértices
em PERM a partir de s. Para cada vértice z fora de PERM matemos a menor
distânciadist[z] de s a z usando caminhos onde o único vértice que não está
em PERM seja z. É necesssário também armazenar o vértice adjacente (precedente)
a z neste caminho em path[z].

Como fazer com que PERM cresça, ou seja, qual vértice deve ser incluído em PERM a
seguir ? Tomamos o vértice, entre todos os que ainda não pertencem a PERM, com
menor distância dist. Acrescentamos então este vértice, chamemo-lo de current,
a PERM, e recalculamos as distâncias (dist) para todos os vértices adjacentes a ele que
não estejam em PERM, pois pode haver um caminho menor a partir de s, passando
por current, do que aquele que havia antes de current ser agregado a PERM. Se houver
um caminho mais curto precisamos também atualizar path[z] de forma a indicar
que current é o vértice adjacente a z pelo novo caminho mínimo.

Vejamos o funcionamento do algoritmo sob uma outra representação:

1) Defini-se inicialmente o nó de origem (raiz), neste caso s, e inclui-se este nó

em PERM. Atribui-se zero a sua distância (dist[s]) porque o custo de ir de s a s é
obviamente 0. Todos os outros nós i tem suas distâncias (dist[i]) inicializadas com um
valor bastante grande ("infinito").
2) A partir de s consulta-se os vértices adjacentes a ele, que no grafo G são u e x. Para
todos os vértices adjacentes, que chamaremos z, calcula-se:
Se dist[z] > dist[s] + peso(s, z)
dist[z] = dist[s] + peso(s, z)
path[z] = s
Fim Se

3) Dentre todos os vértices não pertencentes a PERM escolhe-se aquele com a menor
distância. Neste caso é o vértice x, pois dist[x] = 5.
4) Então, inclui-se x em PERM e a partir de x consulta-se os vértices adjacentes a ele
que não estão em PERM, que no grafo G são u, v e y. Para todos os vértices adjacentes,
que chamaremos z, calcula-se:

Se dist[z] > dist[x] + peso(x, z)

dist[z] = dist[x] + peso(x, z)
path[z] = x
Fim Se

5) Dentre todos os vértices não pertencentes a PERM escolhe-se aquele com a menor
distância. Neste caso é o vértice y, pois dist[y] = 7.

6) Inclui-se então y em PERM e a partir de y consulta-se os vértices adjacentes a ele que

não estão em PERM, que no grafo G é apenas o vértice v. Se dist[v] > dist[y] + peso(y,
v)
dist[v] = dist[y] + peso(y, v)
path[v] = y
Fim Se
7) Dentre todos os vértices não pertencentes a PERM escolhe-se aquele com a menor
distância. Neste caso é o vértice u, pois dist[u] = 8.

8) Inclui-se então u em PERM e a partir de u consulta-se os vértices adjacentes a ele que

não estão em PERM, que no grafo G é apenas o vértice v. Se dist[v] > dist[u] + peso(u,
v)
dist[v] = dist[u] + peso(u, v)
path[v] = u
Fim Se
9) Dentre todos os vértices não pertencentes a PERM escolhe-se aquele com a menor
distância. Neste caso é o único vértice restante v e dist[v] = 9.

10) Por fim faz-se v pertencer a PERM. Neste ponto, todos os vértices já estão
em PERM e a busca é finalizada.

O algoritmo

A estrutura do algoritmo de Dijkstra é muito parecida com a do algoritmo de Prim.

(Embora o algoritmo de Dijkstra, ao contrário do algoritmo de Prim, só se aplique a
custos não-negativos.)

No início de cada iteração, temos uma arborescência T com raiz s. Para qualquer vértice
w fora de T, o custo de w em relação a T é, por definição,

a distância de s a w no digrafo T+F,

sendo F a franja de T. Aqui, a franja de T é o conjunto de todos os arcos que saem de T.

Em outras palavras, o custo de um vértice w que está fora de T é o custo de um caminho
mínimo dentre os que começam em s, terminam em w, e só têm um arco — o último —
fora de T. Diremos que o último arco de um tal caminho mínimo é o arco-pai de w.
Cada iteração do algoritmo de Dijkstra consiste no seguinte:

1. se a franja de T não é vazia

1.1 então seja w um vértice fora de T que tem custo mínimo
1.2 seja e o arco-pai de w
1.3 comece nova iteração com T+e no papel de T
2. senão pare

Nas implementações abaixo, a arborescência T será representada por um vetor pai. O

custo de cada vértice w será armazenado em cst[w] e a ponta inicial do arco-pai de w
será armazenada em fr[w].

As implementações que examinaremos abaixo têm uma peculiaridade: no início da

primeira iteração, a árvore (representada pelo vetor pai) está vazia. Somente a partir do
início da segunda iteração a implementação passa a se comportar de acordo com o
algoritmo.

Implementação para digrafos densos

Suponha que nosso digrafo está representado por sua matriz de adjacência. Como de
hábito, se v-w não é arco então G[v][w] vale maxCST. Supõe-se que o valor de
maxCST é tão grande que não se confunde com o custo de um caminho simples.

1. /* Recebe digrafo G com custos não-

negativos nos arcos e um vértice s. Calcula uma arborescência de caminhos míni
mos com raiz s. A arborescência é armazenada no vetor pai. As distâncias em re
lação a s são armazenadas no vetor cst. */
2.
3. /* A função supõe que a soma dos custos de todas os arcos é estritamente menor
que maxCST. Supõe também que o digrafo tem no máximo maxV vértices. */
4.
5. void dijkstraV1(int s) {
6. int w, w0, fr[maxV];
7. for (w = 0; w < n; w++) {
8. pai[w] = -1;
9. cst[w] = maxCST;
10. }
11. fr[s] = s;
12. cst[s] = 0.0;
13. while (1) {
14. double mincst = maxCST;
15. for (w = 0; w < n; w++) {
16. if (pai[w] == -1 && mincst > cst[w])
17. mincst = cst[w0=w];
18. if (mincst == maxCST) break;
19. pai[w0] = fr[w0];
20. for (w = 0; w < n; w++)
21. if (cst[w] > cst[w0] + G[w0][w]) {
22. cst[w] = cst[w0] + G[w0][w];
23. fr[w] = w0;
24. }
25. }
26. }
Note que essa implementação é quase idêntica à implementação correspondente do
algoritmo de Prim.

Duas observações técnicas:

1. Observe como a comparação de cst[w] com cst[w0] + G[w0][w] trata corretamente
do caso em que w0 e w não são adjacentes e portanto G[w0][w] vale maxCST.
2. Estamos supondo, implicitamente, que maxCST é menor que a metade de
DBL_MAX, de modo que a expressão cst[w0] + G[w0][w] não produz overflow.

No começo de cada iteração (a partir da segunda) temos uma arborescência com raiz s,
representada pelo vetor pai. No início de cada iteração, as seguinte propriedades valem
para cada vértice v:

1. se v está na arborescência então cst[v] é a distância de s a v,

senão, cst[v] é o custo do vértice v em relação à arborescência;

2. se v está fora da arborescência e cst[v] < maxCST então

fr[v] é o penúltimo vértice de um caminho simples de custo cst[v] que liga s a v.

A operação mais característica do algoritmo de Dijkstra é a relaxação de um arco:

1. if (cst[w] > cst[w0] + G[w0][w]) {

2. cst[w] = cst[w0] + G[w0][w];
3. }

Essa operação aparece em toda implementação do algoritmo.

Implementação para digrafos esparsos

A implementação para digrafos representados por vetor de listas de adjacência usa

uma fila de prioridades, tal como a correspondente implementação do algoritmo de
Prim.

1. /* Recebe digrafo G com custos não-

negativos nos arcos e um vértice s. Calcula uma SPT com origem s. A SPT é arma
zenada no vetor pai. As distâncias em relação a s são armazenadas no vetor cst
. */
2.
3. /* A implementação supõe que a soma dos custos de todos os arcos é estritament
e menor que maxCST. Supõe também que o digrafo tem no máximo maxV vértices. *
/
4.
5. void dijkstraEsparso (int s) {
6. int w, w0, fr[maxV], p;
7. PQinit();
8. for (w = 0; w < n; w++)
9. pai[w] = fr[w] = -1;
10. fr[s] = s;
11. cst[s] = 0.0;
12. PQinsert(s);
13. while (!PQempty()) {
14. w0 = PQdelmin();
15. pai[w0] = fr[w0];
16. for (p = 0; p < grau[w0]; p++) {
 17. w = G[w0][p].w;
18. if (fr[w] == -1) {
19. cst[w] = cst[w0] + G[w0][p].cst;
20. PQinsert(w);
21. fr[w] = w0;
22. }
23. else if (cst[w] > cst[w0] + G[w0][p].cst) {
24. cst[w] = cst[w0] + G[w0][p].cst;
25. PQdec(w);
26. fr[w] = w0;
27. }
28. }
29. }
30. }

(Note a operação de relaxação if (cst[w] > cst[w0]+G[w0][p].cst) { cst[w] =

cst[w0]+G[w0][p].cst; } característica do algoritmo de Dijkstra.)

A função dijkstraEsparso usa uma fila de vértices com prioridades definidas pelo vetor
cst. A fila é manipulada pelas seguintes funções:

PQinit(): inicializa uma fila de vértices em que todo vértice v tem prioridade cst[v].
PQempty(): devolve 1 se a fila estiver vazia e 0 em caso contrário.
PQinsert(v): insere o vértice v na fila.
PQdelmin(): retira da fila um vértice de prioridade mínima.
PQdec(v): reorganiza a fila depois que o valor de cst[v] foi decrementado.
A implementação clássica da fila de prioridades usa uma estrutura de heap.

Tal como fizemos com o algoritmo de Prim, podemos organizar a implementação do

algoritmo de Dijkstra de maneira um pouco diferente, inserindo todos os vértices na fila
de prioridades antes mesmo do início do processo iterativo:

1. void dijkstraV2 (int s) {

2. int w, w0, p;
3. PQinit();
4. for (w = 0; w < n; w++) {
5. pai[w] = -1;
6. cst[w] = maxCST;
7. PQinsert(w);
8. }
9. pai[s] = s;
10. cst[s] = 0.0;
11. PQdec(s);
12. while (!PQempty()) {
13. w0 = PQdelmin();
14. if (cst[w0] == maxCST) break;
15. for (p = 0; p < grau[w0]; p++) {
16. w = p->w;
17. if (cst[w] > cst[w0] + G[w0][p].cst) {
18. cst[w] = cst[w0] + G[w0][p].cst;
19. PQdec(w);
20. pai[w] = w0;
21. }
22. }
23. }
24. }