ESCOLA DE ENGENHARIA
C++
Dijkstra e Prim
Algoritmo de Dijkstra (1959)
L=
L=2
Comprimento
Acumulado
2
8
u0
1
u2
1
5
u1
C++ - Dijkstra e Prim
3
u4
6
9
6
9
u7
Prof. Lincoln Cesar Zamboni
9
L=14
L=13
L=
2
8
u10
u9
4
L
L=9
=10
L=
10
7
L
L=11
=12
L=
7
u5
7
2
L=1
L=
9
2
3
L=6
L=
u6
1
2
L=5
L=
u3
6
5
L=7
L=
L=8
L=0
4
1
L=3
L=
3
1
1
L=10
L=
4
11
u8
2/13
Análise
1
2
2
3
3
5
5
0
7
6
7
8
9
6
11
13
1
10
9
11
10
u0= 4
L=
C++ - Dijkstra e Prim
Qual a distância mínima entre os vértices:
•4e1?
Resposta: 2
•4e2?
Resposta: 3
• 4 e 11 ?
Resposta: 10
• 4 e 10 ?
Resposta: 9
•4e8?
Resposta: 13
Qual caminho possui distância
mínima entre os vértices 4 e 8 ?
Prof. Lincoln Cesar Zamboni
3/13
O Caminho do 4 até o 8
Comprimento
Acumulado
L=2,
L=, A
A==40
1
1
Vértice
Anterior
2
L=0, A=0
6
8
4
u2
5
7
C++ - Dijkstra e Prim
L=, A
L=6,
A==20
6
6
9
3
L=
L
L=9,
=10
, A
A==509
10
u7
Prof. Lincoln Cesar Zamboni
7
9
L
=
11,
=11
L=
=12
 , A=
02 L
L=
=14
=13
, A= 0
73
2
7
8
u9
4
L=, A==40
L=1,
u1
9
u5
2
9
3
u4
3
u6
1
L=5,
L=, A
A==20
u3
L=, A==640
L=8,
L=7,
1
5
u0
L=3,
L=, A
A==10
2
2
1
u10
1
4
L=
L
=10
, A=
=10
0
11
u8
4/13
Análise
A=
C++ - Dijkstra e Prim
1
4
2
1
3
u0= 4
5
6
2
0
6
2
7
8
9
11
7
4
10
11
5
10
Qual caminho possui distância mínima
entre os vértices:
•4e8?
Resposta: 8, 7, 11, 10, 5, 6, 2, 1, 4
•4e2?
Resposta: 2, 1, 4
• 4 e 11 ? Resposta: 11, 10, 5, 6, 2, 1, 4
• 4 e 10 ? Resposta: 10, 5, 6, 2, 1, 4
Prof. Lincoln Cesar Zamboni
5/13
Árvore de Caminhos
Mínimos
1
1
2
2
A=
3
9
2
6
8
4
1
5
2
9
C++ - Dijkstra e Prim
1
5
7
3
9
6
6
4
9
10
Prof. Lincoln Cesar Zamboni
7
1
4
2
1
3
2
4
0
5
6
6
2
7
11
8
7
9
4
10
5
11
10
2
7
3
1
1
8
4
11
6/13
Matriz de Pesos (W)
simétrica
C++ - Dijkstra e Prim
77/121 
64% de
nulos
1
2
3
4
5
6
7
8
9
10
11
1
0
1
0
2
6
0
0
0
0
0
0
2
1
0
2
0
5
3
9
0
0
0
0
3
0
2
0
0
0
0
7
9
0
0
0
4
2
0
0
0
8
0
0
0
1
0
0
5
6
5
0
8
0
1
0
0
7
2
0
6
0
3
0
0
1
0
6
0
0
4
0
7
0
9
7
0
0
6
0
2
0
3
1
8
0
0
9
0
0
0
2
0
0
0
4
9
0
0
0
1
7
0
0
0
0
9
0
10
0
0
0
0
2
4
3
0
9
0
1
11
0
0
0
0
0
0
1
4
0
1
0
Prof. Lincoln Cesar Zamboni
7/13
(L)ength, (A)nterior e (M)arcação
L=2,
L=
, A
A==40
1
2
L=0, A=0
8
4
u0
L=3,
L=
, A
A==10
1
u2
u3
6
5
L=
L=8,
L=7,
, A=4
60
3
L=
L=6,
, A=20
5
1
u6
1
u4
9
6
6
7
3
10
9
u7
7
L
=
11,
L
L=
=12
, A
A=11
=0
2
9
L
L=
=14
=13
, A=0
73
2
8
u9
4
L
L=
L=9,
=10
, A==50
9
9
C++ - Dijkstra e Prim
3
u5
7
2
L=
L=1,
, A=40
u1
L=5,
L=
, A
A==20
2
2
L A M
2 4
0 F
T
1 
2 
3 1
F
0 T
1
LL=
=10
,, A=10
=0
11
1
u8
Prof. Lincoln Cesar Zamboni
u10
4
3 
5 2
0
4 0 0
8
0
4
7 6
5 
6 2
0
6 
11 11
12
2
0
7 
13
14 7
3
0
8 
4
1 0
9 
10
5
0
9 9
10 
T
F
FT
FT
FT
FT
FT
FT
FT
10 10
0 FT
11 
8/13
Complexidade Dijkstra
O(n2)
início
n–i–1
comparações e
adições.
n
vértices.
Os vértices V foram
numerados a partir do
número 1.
V = {1, 2, ..., n}
obter o vértice
inicial u0 Î V e o
vértice final uf Î V
M = {u0}
D=V-M
L(u0) é a distância acumulada até u0
e A(u0) é o vértice anterior a u0 –
neste caso 0 significa que não há
um vértice anterior.
L(u0) = 0
A(u0) = 0
Os vértices
desmarcados recebem
a distância acumulada
 e não possuem
vértice anterior
(simbolizado por ter o
valor A(v) nulo).
L(v) = 
A(v) = 0
"vÎD
O caminho para a
distância mínima
de uf até u0 é C
Não existe um
caminho com distância
mínima de uf até u0
v = u0
C é inicializada com a
seqüência ordenada nula ().
ui ¹ uf
não
sim
Expansão da árvore
de caminhos
mínimos. a(ui, v)
representa a
adjacência entre ui
e v.
L(v) = mínimo(L(v),
L(ui) + w(ui, v))
A(v) = ui
"vÎD e a(ui, v) ¹ 0
ui+1 | L(ui+1) = mínimo(L(v))
"vÎD
M = M È {ui+1}
L(uf) é a distância
mínima de u0 até uf.
Busca do vértice
desmarcado com
distância
acumulada mínima.
sim
não
i=0
C = ()
v = uf
não
v ¹ u0 e
A(v) ¹ 0
sim
C = C + (v)
C é concatenada com a
seqüência ordenada
unitária (v).
v = A(v)
O vértice buscado
agora é marcado.
i=i+1
C++ - Dijkstra e Prim
fim
M é o conjunto dos vértices
Marcados e D o dos
Desmarcados.
Prof. Lincoln Cesar Zamboni
n – i – 1 comparações.
9/13
Dijkstra: total de operações com n
vértices
Adições
a = (n-1)+(n-2)+...+
a=
1 + 0
0 + 1 +...+ (n-2)+(n-1)
2a = (n-1)+(n-1)+...+ (n-1)+(n-1)  a = ½ n(n-1)
Comparações
c = n(n-1)
Total
0(n2)
C++ - Dijkstra e Prim
Prof. Lincoln Cesar Zamboni
10/13
Algoritmo de Prim
L=
A=0
L=2A=4
1
1
Distância
u2
2
L=0 A=0
8
4
u3
6
5
L=7
A=9
L=6
A=1
L=5
L=1
A=6
L=8A=2
A=4
L=
A=0
1
5
u0
7
2
L=1
L= A=4
A=0
9
u1
C++ - Dijkstra e Prim
9
L=2 A=2
L=
A=0
3
u4
3
9
7
9
L=
A=0
L=3
L=9A=7
L=4
A=11
A=3
L= A=2
A=0 L=1
L=
A=0 L=2
L=9
A=2
L=7
L=3A=11
A=3
A=10
L=6
A=6
6
2
6
7
8
u5
u6
1
L=A=1
A=0
L=1
2
2
4
3
1
L=4
A=6
L= A=5
A=0 L=
A=0
L=2
L=9
A=9
L=1A=10
10
u7
Prof. Lincoln Cesar Zamboni
u10
u9
1
4
11
u8
11/13
Árvore de Cobertura
Mínima
1
1
2
2
A=
3
9
2
6
8
4
1
5
2
9
C++ - Dijkstra e Prim
1
5
7
3
9
6
6
4
9
10
Prof. Lincoln Cesar Zamboni
7
1
1
11
4
2
1
3
2
4
0
5
6
6
2
7
11
8
7
9
4
10
5
11
10
2
7
3
1
8
4
tot = 16
12/13
Prim
fim
início
Os vértices V foram numerados
a partir do número 1.
V = {1, 2, ..., n}
M é o conjunto dos vértices Marcados
e D o dos Desmarcados.
M = {u0}
D=V-M
A árvore de
cobertura mínima
é T e a soma total
de pesos é tot.
L(u0) é a distância acumulada até
u0 e A(u0) é o vértice anterior a u0
– neste caso 0 significa que não
há um vértice anterior.
L(u0) = 0
A(u0) = 0
L(v) = 
A(v) = 0
"vÎD
Os vértices desmarcados
recebem a distância  e
não possuem vértice
anterior (simbolizado por
ter o valor A(v) nulo).
i=0
Não existe
uma árvore de
cobertura
mínima.
sim
não
v = n+1
T é inicializada com a seqüência
ordenada nula ().
D¹Æ
não
T = ()
tot = 0
v=1
não
sim
L(v) = mínimo(L(v),
w(ui, v))
A(v) = ui
"vÎD e a(ui, v) ¹ 0
Expansão da árvore.
a(ui, v) representa a
adjacência entre ui e
v.
v£ne
A(v) ¹ 0
sim
ui+1 | L(ui+1) = mínimo(L(v))
"vÎD
M = M È {ui+1}
Busca do vértice
desmarcado com
distância mínima.
O vértice buscado
agora é marcado.
tot = tot + L(v)
T é concatenada
com a seqüência
ordenada unitária
de um par
ordenado (v, A(v)).
v=v+1
i=i+1
C++ - Dijkstra e Prim
T = T + ((v, A(v)))
Prof. Lincoln Cesar Zamboni
13/13