Aula05_grafos

Prévia do material em texto

Teoria dos Grafos
Valeriano A. de Oliveira
So
orro Rangel
Silvio A. de Araujo
Departamento de Matemáti
a Apli
ada
antunes�ibil
e.unesp.br, so
orro�ibil
e.unesp.br, saraujo�ibil
e.unesp.br
AULA 5
Caminho mínimo - Algoritmo de Djskstra
Preparado a partir do texto:
Rangel, So
orro. Teoria do Grafos, Notas de aula, IBILCE, Unesp, 2002-2013.
Caminho Mínimo em
Grafos
Caminho Mínimo em Grafos
Introduçao
Caminho Mínimo em Grafos
Teoria dos Grafos (Antunes Rangel&Araujo) � 3
Considere a rede:
s t
a b
cd
9
15
4
2
2
3
35
16
6
5
7
21
Caminho Mínimo em Grafos
Teoria dos Grafos (Antunes Rangel&Araujo) � 4
Dado dois vérti
es nesta rede, queremos determinar o menor 
aminho
entre eles.
Uma primeira questão é 
omo representar os valores asso
iados às
arestas neste grafo. Isto pode ser feito através da matriz de pesos.
Seja D um digrafo simples 
ujas arestas possuem �pesos� asso
iados,
digamos, a 
ada aresta (vi, vj) está asso
iado um número real wij ≥ 0
(que pode representar 
omprimento, distân
ia, valor, et
).
Vamos de�nir wii = 0 para todo i e wij =∞ quando não existe uma
aresta entre os vérti
es vi e vj .
Assim a matriz de pesos é uma matriz n× n de�nida 
omo W = [wij],
onde n é o número de vérti
es.
Exemplo
Caminho Mínimo em Grafos
Teoria dos Grafos (Antunes Rangel&Araujo) � 5
Construir a matriz de pesos para a rede abaixo:
s t
a b
cd
9
15
4
2
2
3
35
16
6
5
7
21
Caminho Mínimo em Grafos
Teoria dos Grafos (Antunes Rangel&Araujo) � 6
Observação 1. Em geral
■ wij 6= wji e
■ wij + wjk pode ser menor ou igual a wik.
Por exemplo, na rede anterior,
wsd + wda = 9 + 4 ≤ 15 = wsa.
O algoritmo que nós vamos ver foi proposto por Dijkstra em 1959 e é
um dos mais e�
ientes até hoje. Vamos supor então que queremos
en
ontrar o 
aminho mínimo entre e na rede a
ima.
Caminho Mínimo em Grafos
Teoria dos Grafos (Antunes Rangel&Araujo) � 6
Observação 2. Em geral
■ wij 6= wji e
■ wij + wjk pode ser menor ou igual a wik.
Por exemplo, na rede anterior,
wsd + wda = 9 + 4 ≤ 15 = wsa.
• O algoritmo que nós vamos ver foi proposto por Dijkstra em 1959 e é
um dos mais e�
ientes até hoje. Vamos supor então que queremos
en
ontrar o 
aminho mínimo entre s e t na rede a
ima.
Idéia do Algoritmo:
Caminho Mínimo em Grafos
Teoria dos Grafos (Antunes Rangel&Araujo) � 7
■ Rotular os vérti
es do digrafo.
■ A partir do vérti
e ini
ial s, pro
eder em direção ao vérti
e �nal t
(seguindo as arestas orientadas) rotulando os vérti
es 
om as suas
distân
ias ao vérti
e s, medida até aquele momento.
■ A 
ada estágio do algoritmo teremos vérti
es que possuem rótulos
temporários e outros rótulos permanentes.
■ O rótulo de um vérti
e vj é feito permanente quando este rótulo
representa a menor distân
ia de s até vj.
■ Começamos asso
iando rótulo permanente igual a zero para o vérti
e
s, e um rótulo temporário igual a ∞ para os outros n− 1 vérti
es do
grafo.
■ A 
ada iteração, um novo vérti
e re
ebe um rótulo permanente de
a
ordo 
om as seguintes regras:
Caminho Mínimo em Grafos
Teoria dos Grafos (Antunes Rangel&Araujo) � 8
1. Cada vérti
e vj 
om um rótulo temporário, re
ebe um novo rótulo
temporário dado por:
min{rótulo de vj, (rótulo de vi) + wij}
onde vi é o vérti
e que re
ebeu rótulo permanente na iteração
anterior e wij é o valor da aresta entre o vérti
e vi e o vérti
e vj.
2. En
ontre o menor valor entre os rótulos temporários.
Este será o rótulo permanente do respe
tivo vérti
e.
Em 
aso de empate sele
ione qualquer um dos 
andidatos e atribua
rótulo permanente ao es
olhido.
� Repetir 1 e 2 até que o vérti
e destino, t, re
eba um rótulo
permanente.
Exemplo
Caminho Mínimo em Grafos
Teoria dos Grafos (Antunes Rangel&Araujo) � 9
Vamos apli
ar a ideia a
ima à rede abaixo:
s t
a b
cd
9
15
4
2
2
3
35
16
6
5
7
21
Apli
ação do algoritmo:
Caminho Mínimo em Grafos
Teoria dos Grafos (Antunes Rangel&Araujo) � 10
Ini
ializaçao: rot(s) = 0 é permanente,
rot(a) = rot(b) = rot(c) = rot(d) = rot(t) =∞ são temporários
it = 1
Regra 1 � Novo rótulo
Novo rot(a) = min{∞, 0 + wsa} = min{∞, 15} = 15
Novo rot(b) = min{∞, 0 + wsb} = min{∞,∞} =∞
Novo rot(c) = min{∞, 0 + wsc} = min{∞,∞} =∞
Novo rot(d) = min{∞, 0 + wsd} = min{∞, 9} = 9
Novo rot(t) = min{∞, 0 + wst} = min{∞,∞} =∞
Regra 2 � Rótulo permanente
min{15,∞,∞, 9,∞} = 9 ⇒ rot(d) torna-se permanente
Apli
ação do algoritmo 
ont.:
Caminho Mínimo em Grafos
Teoria dos Grafos (Antunes Rangel&Araujo) � 11
it = 2
Regra 1 � Novo rótulo
Novo rot(a) = min{15, 9 + wda} = min{15, 9 + 4} = 13
Novo rot(b) = min{∞, 9 + wdb} = min{∞,∞} =∞
Novo rot(c) = min{∞, 9 + wdc} = min{∞, 9 + 2} = 11
Novo rot(t) = min{∞, 9 + wdt} = min{∞,∞} =∞
Regra 2 � Rótulo permanente
min{13,∞, 11,∞} = 11 ⇒ rot(c) torna-se permanente
Regra 1 � Novo rótulo
Novo
Novo
Novo
Regra 2 � Rótulo permanente
torna-se permanente
Apli
ação do algoritmo 
ont.:
Caminho Mínimo em Grafos
Teoria dos Grafos (Antunes Rangel&Araujo) � 11
it = 2
Regra 1 � Novo rótulo
Novo rot(a) = min{15, 9 + wda} = min{15, 9 + 4} = 13
Novo rot(b) = min{∞, 9 + wdb} = min{∞,∞} =∞
Novo rot(c) = min{∞, 9 + wdc} = min{∞, 9 + 2} = 11
Novo rot(t) = min{∞, 9 + wdt} = min{∞,∞} =∞
Regra 2 � Rótulo permanente
min{13,∞, 11,∞} = 11 ⇒ rot(c) torna-se permanente
it = 3
Regra 1 � Novo rótulo
Novo rot(a) = min{13, 11 + wca} = min{13, 11 +∞} = 13
Novo rot(b) = min{∞, 11 + wcb} = min{∞, 11 +∞} =∞
Novo rot(t) = min{∞, 11 + wct} = min{∞, 11 + 7} = 18
Regra 2 � Rótulo permanente
min{13,∞, 18} = 13 ⇒ rot(a) torna-se permanente
Apli
ação do algoritmo 
ont.:
Caminho Mínimo em Grafos
Teoria dos Grafos (Antunes Rangel&Araujo) � 12
it = 4
Regra 1 � Novo rótulo
Novo rot(b) = min{∞, 13 + wab} = min{∞, 13 + 35} = 48
Novo rot(t) = min{18, 13 + wat} = min{18, 13 +∞} = 18
Regra 2 � Rótulo permanente
min{48, 18} = 18 ⇒ rot(t) torna-se permanente
Fim
Podemos parar pois o vérti
e destino, , re
ebeu rótulo permanente.
Assim o menor 
aminho entre e tem 
omprimento igual a 18.
Como re
uperar o 
aminho? A partir do vérti
e destino , veri�
amos o
vérti
e 
om rótulo permanente usado na obtenção do rótulo de . No
nosso exemplo, o vérti
e .
Repetimos o pro
esso a partir de até al
ançar o vérti
e ini
ial . Assim
temos . O 
aminho é obtido invertendo a ordem obtida: .
Apli
ação do algoritmo 
ont.:
Caminho Mínimo em Grafos
Teoria dos Grafos (Antunes Rangel&Araujo) � 12
it = 4
Regra 1 � Novo rótulo
Novo rot(b) = min{∞, 13 + wab} = min{∞, 13 + 35} = 48
Novo rot(t) = min{18, 13 + wat} = min{18, 13 +∞} = 18
Regra 2 � Rótulo permanente
min{48, 18} = 18 ⇒ rot(t) torna-se permanente
Fim
Podemos parar pois o vérti
e destino, t, re
ebeu rótulo permanente.
Assim o menor 
aminho entre s e t tem 
omprimento igual a 18.
Como re
uperar o 
aminho? A partir do vérti
e destino t, veri�
amos o
vérti
e 
om rótulo permanente usado na obtenção do rótulo de t. No
nosso exemplo, o vérti
e c.
Repetimos o pro
esso a partir de c até al
ançar o vérti
e ini
ial s. Assim
temos t, c, d, s. O 
aminho é obtido invertendo a ordem obtida: s, d, c, t.
Implementação
Caminho Mínimo em Grafos
Teoria dos Grafos (Antunes Rangel&Araujo) � 13
Em uma possível implementação deste algoritmo vamos pre
isar
armazenar as seguintes informações:
■ Indi
ação se um vérti
e vk possui rótulo permanente ou temporário.
■ Guardar a menor distân
ia entre o vérti
e ini
ial s e o vérti
e vk.■ Guardar o vérti
e 
om rótulo permanente que deu origem a um novo
rótulo (importante para re
uperar o 
aminho).
Assim vamos podemos de�nir a seguinte estrutura de dados:
1. Entrada de Dados: Matriz de pesos W (O(n2)).
2. A di�
uldade é distinguir, a 
ada iteração, os vérti
es 
om rótulos
permanentes e os vérti
es 
om rótulo temporário.
Utilizamos um vetor lógi
o (ou binário) n-dimensional:
final(v) =
{
True se o rótulo do vérti
e v é permanente,
False se o rótulo do vérti
e v é temporário.
Caminho Mínimo em Grafos
Teoria dos Grafos (Antunes Rangel&Araujo) � 14
3. Pre
isamos também de um vetor n-dimensional para guardar as
distân
ias a
umuladas do vérti
e ini
ial s ao vérti
e vk. Vamos
hamar este vetor de dist.
4. Como re
uperar o 
aminho? Sabemos que a menor distân
ia será
dada por dist(t). Mas qual é este 
aminho?
Cada vez que o rótulo de um vérti
e é modi�
ado pre
isamos saber
a partir de que vérti
e foi 
al
ulado o novo rótulo. Mantendo um
vetor n-dimensional pred tal que:
• pred(v) indi
a o vérti
e 
om rótulo permanente que deu origem
ao rótulo do véti
e v,
• e se v for o vérti
e ini
ial, então pred(s) = −1;
temos que o menor 
aminho é dado por:
s, pred(pred(· · · )), . . . , pred(pred(t)), pred(t), t.
Caminho Mínimo em Grafos
Teoria dos Grafos (Antunes Rangel&Araujo) � 15
Considere um digrafo D(V,A), 
om n vérti
es e sua matriz de pesos
W = [wij ], n× n.
Queremos en
ontrar o menor 
aminho entre o vérti
e s e o vérti
e t no
digrafo D.
De�na os vetores:
■ final(i) � indi
a se o vérti
e vi re
ebeu rótulo permanente
(poten
ial) ou não;
■ dist(i) � indi
a a distân
ia a
umulada do vérti
e ini
ial s até o
vérti
e vi;
■ pred(i) � indi
a o vérti
e 
om rótulo permanente que deu origem ao
rótulo do véti
e vi.
Algoritmo de Dijkstra
Caminho Mínimo em Grafos
Teoria dos Grafos (Antunes Rangel&Araujo) � 16
Ini
ialização
para todo v ∈ V faça
iní
io
dist(v) =∞
final(v) = falso
pred(v) = −1
�m
dist(s) = 0
final(s) = verdadeiro
recente = s
Algoritmo de Dijkstra 
ont.
Caminho Mínimo em Grafos
Teoria dos Grafos (Antunes Rangel&Araujo) � 17
Iteração Prin
ipal
enquanto final(t) = falso faça
iní
io
para todo vérti
e vj tal que exista a aresta (recente, vj) e tal que final(j) = falso faça
iní
io (atualização dos rótulos)
rotulo = dist(recente) + wrecente,j
(o rótulo de vj é modi�
ado se houver um 
aminho menor de s a vj através do vérti
e
re
ente)
se rotulo < dist(j) então
iní
io
dist(j) = rotulo
pred(j) = recente
�m
�m
(en
ontre o vérti
e 
om menor rótulo temporário)
Seja y o vérti
e 
om menor rótulo temporário, tal que dist(y) 6=∞
iní
io (o rótulo do vérti
e y se torna permanente)
final(y) = verdadeiro
recente = y
�m
�m
Exemplo
Caminho Mínimo em Grafos
Teoria dos Grafos (Antunes Rangel&Araujo) � 18
Rastrear o algoritmo de Dijkstra usando o digrafo 
om vérti
es
s, a, b, c, d, t 
uja matriz de pesos asso
iada é:
W =


0 7 4 9 7 ∞
7 0 1 ∞ ∞ 6
4 1 0 3 ∞ ∞
9 ∞ 3 0 1 3
7 ∞ ∞ 1 0 5
∞ 6 ∞ 3 5 0


.
Exemplo 
ont.
Caminho Mínimo em Grafos
Teoria dos Grafos (Antunes Rangel&Araujo) � 19
Ini
ialização
dist = [∞ ∞ ∞ ∞ ∞ ∞]
final = [falso falso falso falso falso falso]
pred = [−1 − 1 − 1 − 1 − 1 − 1]
dist(s) = 0
final(s) = verdadeiro
recente = s
it = 1
Vérti
es v tais que existe a aresta (recente, v) e tais que
final(v) = falso: a, b, c, d
Exemplo 
ont.
Caminho Mínimo em Grafos
Teoria dos Grafos (Antunes Rangel&Araujo) � 20
v = a: rotulo = dist(recente) + wrecente,a = 0 + 7 <∞ = dist(a)
dist(a) = 7
pred(a) = s
v = b: rotulo = dist(recente) + wrecente,b = 0 + 4 <∞ = dist(b)
dist(b) = 4
pred(b) = s
v = c: rotulo = dist(recente) + wrecente,c = 0 + 9 <∞ = dist(c)
dist(c) = 9
pred(c) = s
v = d: rotulo = dist(recente) + wrecente,d = 0 + 7 <∞ = dist(d)
dist(d) = 7
pred(d) = s
Exemplo 
ont.
Caminho Mínimo em Grafos
Teoria dos Grafos (Antunes Rangel&Araujo) � 21
Vérti
e y 
om menor rótulo temporário, tal que dist(y) 6=∞: b
final(b) = verdadeiro
recente = b
Vérti
es tais que existe a aresta e tais que
:
:
:
Exemplo 
ont.
Caminho Mínimo em Grafos
Teoria dos Grafos (Antunes Rangel&Araujo) � 21
Vérti
e y 
om menor rótulo temporário, tal que dist(y) 6=∞: b
final(b) = verdadeiro
recente = b
it = 2
Vérti
es v tais que existe a aresta (recente, v) e tais que
final(v) = falso: a, c
v = a: rotulo = dist(recente) + wrecente,a = 4 + 1 < 7 = dist(a)
dist(a) = 5
pred(a) = b
v = c: rotulo = dist(recente) + wrecente,c = 4 + 3 < 9 = dist(c)
dist(c) = 7
pred(b) = b
Exemplo 
ont.
Caminho Mínimo em Grafos
Teoria dos Grafos (Antunes Rangel&Araujo) � 22
Vérti
e y 
om menor rótulo temporário, tal que dist(y) 6=∞: a
final(a) = verdadeiro
recente = a
Vérti
es tais que existe a aresta e tais que
:
:
Vérti
e 
om menor rótulo temporário, tal que : ou
Exemplo 
ont.
Caminho Mínimo em Grafos
Teoria dos Grafos (Antunes Rangel&Araujo) � 22
Vérti
e y 
om menor rótulo temporário, tal que dist(y) 6=∞: a
final(a) = verdadeiro
recente = a
it = 3
Vérti
es v tais que existe a aresta (recente, v) e tais que
final(v) = falso: t
v = t: rotulo = dist(recente) + wrecente,t = 5 + 6 <∞ = dist(t)
dist(t) = 11
pred(t) = a
Vérti
e y 
om menor rótulo temporário, tal que dist(y) 6=∞: c ou d
final(c) = verdadeiro
recente = c
Exemplo 
ont.
Caminho Mínimo em Grafos
Teoria dos Grafos (Antunes Rangel&Araujo) � 23
it = 4
Vérti
es v tais que existe a aresta (recente, v) e tais que
final(v) = falso: d, t
v = d: rotulo = dist(recente) + wrecente,d = 7 + 1 ≮ 7 = dist(d)
v = t: rotulo = dist(recente) + wrecente,t = 7 + 3 < 11 = dist(t)
dist(t) = 10
pred(t) = c
Vérti
e y 
om menor rótulo temporário, tal que dist(y) 6=∞: d
final(d) = verdadeiro
recente = d
Exemplo 
ont.
Caminho Mínimo em Grafos
Teoria dos Grafos (Antunes Rangel&Araujo) � 24
it = 5
Vérti
es v tais que existe a aresta (recente, v) e tais que
final(v) = falso: t
v = t: rotulo = dist(recente) + wrecente,d = 7 + 5 ≮ 7 = dist(d)
Vérti
e y 
om menor rótulo temporário, tal que dist(y) 6=∞: t
final(t) = verdadeiro
recente = t
Como final(t) = verdadeiro, pare
Exemplo 
omt.
Caminho Mínimo em Grafos
Teoria dos Grafos (Antunes Rangel&Araujo) � 25
Qual é o valor do menor 
aminho?
dist(t) = 10
Qual é este 
aminho?
t, pred(t)
t, c, pred(c)
t, c, b, pred(b)
t, c, b, s, pred(s)
t, c, b, s,−1
O menor 
aminho é {s, b, c, t}
Exemplo 
ont.
Caminho Mínimo em Grafos
Teoria dos Grafos (Antunes Rangel&Araujo) � 26
E se quisermos o menor 
aminho entre s e c? Podemos aproveitar os
ál
ulos anteriores.
Como c possui rótulo permanente, temos que:
dist(c) = 7
E o 
aminho é:
c, pred(c)
c, b, pred(b)
c, b, s
O menor 
aminho é então: {s, b, c}.
Observações
Caminho Mínimo em Grafos
Teoria dos Grafos (Antunes Rangel&Araujo) � 27
1. A 
omplexidade em termos de tempo 
omputa
ional do algoritmo
a
ima é dada por:
O laço prin
ipal deste algoritmo, no pior 
aso, é exe
utado n− 1
vezes. Isto a
onte
e quando o vérti
e �nal, t, é o último a re
eber
um rótulo permanente. Para 
ada exe
ução deste laço, pre
isamos
examinar uma linha da matriz de pesos, e atualizar os vetores dist e
pred, ou seja um tempo propor
ional a n. Assim o tempo total é da
ordem 2n(n− 1). A 
omplexidade é O(n2).
Observe que independe do número de arestas no grafo.
2. É possível, usando o algoritmo de Dijkstra en
ontrar o menor
aminho entre o vérti
e s e todos os outros vérti
es do grafo.O que
deve ser modi�
ado?
Observações
Caminho Mínimo em Grafos
Teoria dos Grafos (Antunes Rangel&Araujo) � 28
1. Outros Algoritmos para problemas de Caminho Mínimo em grafos
podem ser en
ontrados por exemplo na página 283 de: [Otimização
Combinatória e Programação Linear, M.C. Goldbarg e H.P.L. Luna,
Ed. Campus, 2000℄.
2. O algoritmo de Dijskstra fun
iona apenas se wij ≥ 0 para todos i, j.
Veri�que este fato apli
ando o algoritmo à seguinte rede para
en
ontrar o menor 
aminho entre v1 e v3:
v1
v2 v3
1
-5
5
	Caminho Mínimo em Grafos
	Introduçao
	
	Exemplo
	
	Idéia do Algoritmo:
	
	Exemplo
	Aplicação do algoritmo:
	Aplicação do algoritmo cont.:
	Aplicação do algoritmo cont.:
	Implementação
	
	
	Algoritmo de Dijkstra
	Algoritmo de Dijkstra cont.
	Exemplo
	Exemplo cont.
	Exemplo cont.
	Exemplo cont.
	Exemplo cont.
	Exemplo cont.
	Exemplo cont.
	Exemplo comt.
	Exemplo cont.
	Observações
	Observações