Aula 3
Algoritmo de Dijkstra
Caminhamento em Grafos
ATP4
1
Algoritmo de Dijkstra (1975)
• Considere um grafo G = (V,E), cujas arestas possuem
pesos não-negativos
• O Algoritmo de Dijkstra resolve o problema dos caminhos
mais curtos de única origem
• Estruturas de dados:
– E(x,y): existe aresta de x para y?
– w(x,y): peso da aresta de x para y
– incluídos: conjunto dos vértices cujos menores caminhos a
partir do inicial já são conhecidos
– borda: conjunto dos vértices candidatos à próxima escolha
– antecessor[x]: vértice antecessor de x no menor caminho
– custo[x]: custo do caminho até x
ATP4
2
Algoritmo de Dijkstra...
DIJKSTRA(Grafo G, int v0)
borda = {v0}; incluídos = {}; antecessor[x] = -1, x
custo[x] = , x; custo[v0] = 0;
Enquanto borda não vazia faça
v = vértice da borda com o menor custo
insira v em incluídos; retire v da borda
para todo x = 1,...,G.n, tq (x  incluídos)
se E(v,x) e (custo[x] > custo[v] + w(v,x))
custo[x] = custo[v] + w(v,x);
insira x na borda
antecessor[x] = v
ATP4
3
Algoritmo de Dijkstra...
Ant
-
-
-
A
6
B
-
0
5
C




B
C
2
6
D
C
A
5
5
3
-
6
E
D
E
3
ATP4
4
Algoritmo de Dijkstra...
Ant
-
A
-
A
6
B
A
0
6
C
B

6

5
A
C
5
2
6
D
C
5
5
5
3
-
6
E
D
E
3
ATP4
5
Algoritmo de Dijkstra...
Ant
-
A
E
A
6
B
C
5
0
6
C
6
7
11
6
E
5
A
B
C
5
2
6
D
A
5
5
3
E
2
D
6
E
3
ATP4
6
Algoritmo de Dijkstra...
Ant
-
A
E
A
6
B
0
6
C
2
6
C
5
6
D
A
5
5
3
B
E
B
6
7
9
5
A
C
5
3
2
D
E
3
ATP4
7
Algoritmo de Dijkstra...
Ant
-
A
E
A
6
B
0
6
C
2
6
C
5
6
D
A
5
5
3
B
E
B
6
7
9
5
A
C
5
3
2
D
E
3
ATP4
8
Algoritmo de Dijkstra...
Ant
-
A
E
A
6
B
0
6
C
2
6
C
5
6
D
A
5
5
3
B
E
B
6
7
9
5
A
C
5
3
2
D
E
3
ATP4
9
Algoritmo de Dijkstra
• Análise da eficiência:
– Para grafos densos utilizando matrizes de
adjacências, tempo de execução é O(n2).
– Para grafos esparsos, utilizando listas de
adjacências, tempo de execução é O(e
log(n)).
ATP4
10
Busca em Profundidade
• A busca em profundidade é uma forma de visitar
todos os vértices de modo sistemático
• Pequenas modificações no algoritmo podem nos dar
informações bastante interessantes sobre o grafo
• Estruturas de dados:
– boolean marcado[1..n]
marcado[v] = false, para todo v
– int antecessor[1..n]
antecessor[v] = 0, para todo v
ATP4
11
Busca em Profundidade...
void BuscaProfundidade(int v) {
marcado[v] = true;
para w = 1,2,...,n faça {
se E(v,w) e ! marcado[w] {
antecessor[w] = v;
BuscaProfundidade(w);
}
}
}
ATP4
12
Busca em Profundidade...
void BuscaProfundidade(int v) {
marcado[v] = true;
P.empilha(v);
enquanto ! P.vazia() faça {
w = P.desempilha();
para z = 1,2,...,n faça {
se E(z,w) e ! marcado[z] {
antecessor[z] = w;
marcado[z] = true;
P.empilha(z);
}
}
}
}
ATP4
13
Busca em Amplitude...
void BuscaAmplitude(int v) {
marcado[v] = true;
F.insere(v);
enquanto ! F.vazia() faça {
w = P.retira();
para z = 1,2,...,n faça {
se E(z,w) e ! marcado[z]{
antecessor[z] = w;
marcado[z] = true;
P.insere(z);
}
}
}
}
ATP4
14