Anlise de Complexidade
do Algoritmo de Dijkstra
Complexidade depende da
implementao
Algoritmo de Dijkstra
Input: Grafo G (dirigido ou no), vrtice S, cada aresta e tem uma dist(e)
associada.
Output: para cada vrtice v, dist(v) de S a v, distncia do menor caminho entre S
e v.
1.
Para todo vrtice u
2.
dist(u) = infinito
3.
prev(u) = nil
4.
dist(S) = 0
5.
Constri H = fila com prioridade contendo os vrtices de G (prioridade a
menor distncia a seus filhos)
6.
While H
7.
u = deletemin(H)
8.
Para cada aresta uv (arestas so ordenadas em ordem descrescente das
distncias)
9.
10.
11.
12.
se dist(v) > dist(u) + dist(u,v)
dist(v) = dist(u) + dist(u,v)
prev(v) = u
Ajusta_valor(H,v) (v recolocado na fila com sua prioridadade
ajustada)
Anlise de Complexidade
1. Para todo vrtice u
Custo constante c1
2. dist(u) = infinito
3. prev(u) = nil Custo constante c2
O(|V|) vezes
O(|V|)
constante c3; Executada 1 vez
4. dist(S) =Custo
0
X = Custo de inserir
elemento no array
5. Constri H = fila com prioridade contendo os vrtices deExecutada
G
|V| vezes
. While H
O(|V|) vezes
.
u = deletemin(H)
.
Para cada aresta uv
O(|E|) vezes
.
se dist(v) > dist(u) + dist(u,v)
Custo c4
0.
dist(v) = dist(u) + dist(u,v)
Custo constante c5
1.
prev(v) = u
Custo constante c6
2.
Ajusta_dist(H,v)
Custo Y; Executada
O(|V|) vezes
Custo Z; Executada
O(|V|+|E|) vezes
(|V|) + c3 + X.(O(|V|) + Y.O(|V|) + (Z + c4+c5+c6) O(|E|+|V|) =
O(|V|) + X + Y.O(|V|) + Z. O(|E|+|V|)
Anlise de Complexidade: depende da
implementao da fila com prioridades
Fila = array no ordenado de valores (status) para os
vrtices do grafo.
Exemplo: 3 vrtices
4
A
2
C
A
0
B inf
C inf
B
C
4
2
1
Fila na iterao
zero, considerando
a ordem dos vrtices A < B < C
Se a ordem fosse B < A < C o array seria :[inf, 0, inf]
Custos das operaes de fila
implementada como array
Custo X = insere elemento no array = custo constante
O(1)
Custo Y = deletemin(H) = scan no array = O(|V|)
Custo Z = Ajusta_dist(H,v) = altera o status do vrtice v
= custo constante O(1)
Complexidade total =
O(|V|) + X O(|V|)+ Y.O(|V|) + Z. O(|V|+|E|) =
O(|V|) + O(|V|) + O(|V|) O(|V|) + O(|E|+|V|) = O(|V|2 + |E|) =
O(|V|2 ) j que |E| |V|2
Anlise de Complexidade: depende da
implementao da fila com prioridades
Fila = heap binrio
Cada nvel completamente
preenchido da esquerda para a direira
antes que prximo nivel (abaixo) seja criado
e comece a ser preenchido baixo comece a se
preenchido
Custo da operao de inserir um
elemento no heap
Custo da operao de inserir um
elemento no heap
Custo da operao de inserir um
elemento no heap
Insere no primeiro lugar livre +
Bubble-up
O(log|V|)
Custo da operao de
deletemin
3
Custo da operao de
deletemin
Deleta a raiz + siftdown
O(1) + log(|V|) = log(|V|)
Custo da operao de ajustar (diminuir) um elemento no heap
Custo da operao de ajustar (diminuir) um elemento no heap
10
Altera valor + bubble-up
O(1) + log(|V|) = log(|V|
Custos das operaes de fila
implementada como heap bin
Custo X = insere elemento no array = O(log|V|)
Custo Y = deletemin(H) = O(log|V|)
Custo Z = Ajusta_dist(H,v) = altera o status do vrtice v
= = O(log|V|)
Complexidade total =
O(|V|) + X O(|V|)+ Y.O(|V|) + Z. O(|V|+|E|) =
O(|V|) + O(log|V|).O(|V|) + O(log|V|).O(|V|) +
O(log|V|).O(|V|+|E|) = O(log|V|).O(|V|+|E|)