Análise e Síntese de Algoritmos
Caminhos Mais Curtos
CLRS, Cap. 24
Contexto
• Algoritmos elementares em grafos
• Grafos não dirigidos:
– Árvores abrangentes de menor custo
• Grafos dirigidos:
– Caminhos mais curtos
• Fonte única
• Entre todos os pares
• Redes de fluxo (grafos dirigidos com arcos capacitados)
– Fluxos máximos
– Fluxos de custo mínimo
2003/2004
Análise e Síntese de Algoritmos
2
Resumo
• Caminhos Mais Curtos
– Definições
• Caminhos Mais Curtos com Fonte Única (SSSPs)
– Propriedades
• Relaxações
– Algoritmo de Dijkstra
– Algoritmo de Bellman-Ford
– SSSPs em DAGs
2003/2004
Análise e Síntese de Algoritmos
3
Caminhos Mais Curtos
• Dado um grafo G = (V, E), dirigido, com uma função de pesos
w : E  R, define-se o peso de um caminho p, p = v0,v1,…,vk,
como a soma dos pesos dos arcos que compõem p:
k
w p   w v i1, v i 
i 1
• O peso do caminho mais curto de u para v é definido por:

p
min w p : u 
v
u, v   


se existe caminho de u para v
caso contrário
• Um caminho mais curto de u para v é qualquer caminho p tal
que w(p) = (u,v)
2003/2004
Análise e Síntese de Algoritmos
4
Problemas de Caminhos Mais Curtos
• Caminhos Mais Curtos com Fonte Única (SSSPs)
– Identificar o caminho mais curto de um vértice fonte s  V
para qualquer outro vértice v  V
• Caminhos Mais Curtos com Destino Único
– Identificar o caminho mais curto de qualquer vértice v  V
para um vértice destino t  V
• Caminho Mais Curto entre Par Único
– Identificar caminho mais curto entre dois vértices u e v
• Caminhos Mais Curtos entre Todos os Pares (APSPs)
– Identificar um caminho mais curto entre cada par de vértices
de V
2003/2004
Análise e Síntese de Algoritmos
5
Ciclos Negativos
• Arcos podem ter pesos com valor negativo
• É possível a existência de ciclos com peso total
negativo
– Se ciclo negativo não atingível a partir da fonte s  (s,v)
bem definido
– Se ciclo negativo atingível a partir da fonte s
• pesos dos caminhos mais curtos não são bem definidos
• é sempre possível encontrar um caminho mais curto de s
para qualquer vértice incluído no ciclo
• define-se (s,v) = -
2003/2004
Análise e Síntese de Algoritmos
6
Ciclos Negativos (Cont.)
• Identificação de ciclos negativos:
– Alguns algoritmos requerem pesos não negativos
• Dijkstra
– Alguns algoritmos identificam ciclos negativos e reportam a
sua existência
• Bellman-Ford
• Exemplo:
s
3
3
x
-5
2003/2004
y
z
-2
w(s,x,y,z) = 4
w(s,x,y,x,y,z) = 2
w(s,x,y,x,y,x,y,z) = 0
…
Análise e Síntese de Algoritmos
7
Representação de Caminhos Mais
Curtos
• Para cada vértice v  V associar predecessor [v]
– Após identificação dos caminhos mais curtos, [v] identifica
vértice anterior a v em caminho mais curto de s para v
• Sub-grafo de predecessores G = (V, E):
V  v  V : v   NIL  s
E   v , v   E : v  V  s
2003/2004
Análise e Síntese de Algoritmos
8
Representação de Caminhos Mais
Curtos (Cont.)
• Uma árvore de caminhos mais curtos é um sub-grafo
dirigido G’ = (V’, E’), V’  V e E’  E, tal que:
– V’ é o conjunto de vértices atingíveis a partir de s em G
– G’ forma uma árvore com raiz s
– Para todo o v  V’, o único caminho de s para v em G’ é um
caminho mais curto de s para v em G
• OBS: Após identificação dos caminhos mais curtos de
G, G’ é dado por G = (V, E)
• OBS: Dado G = (V, E), G’ não é necessariamente único
2003/2004
Análise e Síntese de Algoritmos
9
Estudo dos SSSPs
• Sub-estrutura óptima: (sub-caminhos de caminhos
mais curtos são caminhos mais curtos)
24.1
– Seja p = v1,v2,…,vk um caminho mais curto entre v1 e vk, e
seja pij = vi,vi+1,…,vj um sub-caminho de p entre vi e vj.
Então pij é um caminho mais curto entre vi e vj
• Se existisse caminho mais curto entre vi e vj então seria
possível construir caminho entre v1 e vk mais curto do
que p; uma contradição !
2003/2004
Análise e Síntese de Algoritmos
10
Estudo dos SSSPs
– Seja p = s,…,v um caminho mais curto entre s e v, que pode ser
decomposto em p’ = s,…,u e (u,v). Então (s,v) = (s,u) + w(u,v)
• p’ é caminho mais curto entre s e u
24.1
• (s,v) = w(p) = w(p’) + w(u,v) = (s,u) + w(u,v)
24.10
– Para todos os arcos (u,v)  E verifica-se (s,v)  (s,u) + w(u,v)
• Caminho mais curto de s para v não pode ter mais peso do
que qualquer outro caminho de s para v
• Assim, peso do caminho mais curto de s para v não superior
ao peso do caminho mais curto de s para u seguido do arco
(u,v) (i.e. exemplo de um dos caminhos de s para v)
2003/2004
Análise e Síntese de Algoritmos
11
Estudo dos SSSPs (Cont.)
• Relaxação:
– Algoritmos para SSSPs utilizam relaxação
– d[v]: limite superior no valor do peso do caminho mais curto
entre s e v; estimativa do caminho mais curto
Initialize-Single-Source(G,s)
for v  V[G]
d[v] = 
[v] = NIL
d[s] = 0
Relax(u,v,w)
if d[v] > d[u] + w(u,v)
d[v] = d[u] + w(u,v)
[v] = u
– Algoritmos para SSSPs aplicam sequência de relaxações
dos arcos de G após inicialização
2003/2004
Análise e Síntese de Algoritmos
12
Estudo dos SSSPs (Cont.)
• Propriedades da relaxação:
24.13
– Após relaxar arco (u,v), d[v]  d[u] + w(u,v)
• Se d[v] > d[u] + w(u,v) antes da relaxação, então d[v] =
d[u] + w(u,v) após relaxação
• Se d[v]  d[u] + w(u,v) antes da relaxação, então d[v] 
d[u] + w(u,v) após relaxação
• Em qualquer caso, d[v]  d[u] + w(u,v) após relaxação
2003/2004
Análise e Síntese de Algoritmos
13
Estudo dos SSSPs (Cont.)
• Propriedades da relaxação:
24.11
– d[v]  (s, v) para qualquer v  V e para qualquer sequência de
passos de relaxação nos arcos de G. Se d[v] atinge o valor (s,v)
então o valor não é mais alterado
• d[v]  (s, v) é válido após inicialização
• Prova por contradição.
– Seja v o primeiro vértice para o qual a relaxação do arco (u,v)
causa d[v] < (s, v)
24.10
– Após relaxar arco: d[u] + w(u,v) = d[v] < (s, v)  (s, u) + w(u,v)
– Pelo que, d[u] < (s, u) antes da relaxação de (u,v); contradição !
• Após ter d[v] = (s, v), o valor de d[v] não pode decrescer; e
pela relaxação também não pode crescer !
2003/2004
Análise e Síntese de Algoritmos
14
Estudo dos SSSPs (Cont.)
• Propriedades da relaxação:
24.14
– Seja p = s,…,u,v um caminho mais curto em G, e seja
Relax(u,v,w) executada no arco (u,v). Se d[u] = (s, u) antes
da chamada a Relax(u,v,w), então d[v] = (s, v) após a
chamada a Relax(u,v,w)
• Se d[u] = (s, u) então valor de d[u] não é mais alterado
• Após relaxar arco (u,v): d[v]  d[u] + w(u,v) = (s, u) +
24.1
w(u,v) = (s, v)
• Mas, d[v]  (s, v), pelo que d[v] = (s, v), e não se altera !
24.11
2003/2004
Análise e Síntese de Algoritmos
15
Estudo dos SSSPs (Revisão)
24.1
– Seja p = v1,v2,…,vk um caminho mais curto entre v1 e vk, e
seja pij = vi,vi+1,…,vj um sub-caminho de p entre vi e vj.
Então pij é um caminho mais curto entre vi e vj
– Seja p = s,…,v um caminho mais curto entre s e v, que
pode ser decomposto em p’ = s,…,u e (u,v). Então (s,v) =
(s,u) + w(u,v)
24.10
– Para todos os arcos (u,v)  E verifica-se (s,v)  (s,u) +
w(u,v)
2003/2004
Análise e Síntese de Algoritmos
16
Estudo dos SSSPs (Revisão)
• Propriedades da relaxação:
24.13
24.11
24.14
– Após relaxar arco (u,v), d[v]  d[u] + w(u,v)
– d[v]  (s, v) para qualquer v  V e para qualquer sequência
de passos de relaxação nos arcos de G. Se d[v] atinge o
valor (s,v) então o valor não é mais alterado
– Seja p = s,…,u,v uma caminho mais curto em G, e seja
Relax(u,v,w) executada no arco (u,v). Se d[u] = (s, u) antes
da chamada a Relax(u,v,w), então d[v] = (s, v) após a
chamada a Relax(u,v,w)
– …
2003/2004
Análise e Síntese de Algoritmos
17
Algoritmo de Dijkstra — Organização
• Todos os arcos com pesos não negativos
• Algoritmo Greedy
• Algoritmo mantém conjunto de vértices S com pesos
dos caminhos mais curtos já calculados
• A cada passo algoritmo selecciona vértice u em V - S
com menor estimativa do peso do caminho mais
curto
– vértice u é inserido em S
– arcos que saem de u são relaxados
• Fila de prioridade Q é mantida e actualizada com
operações de relaxação
2003/2004
Análise e Síntese de Algoritmos
18
Algoritmo de Dijkstra — Pseudo-Código
O(V)
Dijkstra(G,w,s)
Initialize-Single-Source(G,s)
S=
Q = V[G]
while Q  
u = Extract_Min(Q)
S = S  {u}
foreach v  Adj[u]
Relax(u,v,w)
• Exemplo
2003/2004
// Fila de prioridade Q
O(lg V)
// Actualizar Q
O(E)
Análise e Síntese de Algoritmos
O(lg V)
19
Algoritmo de Dijkstra vs. Alg. de Prim
MST-Prim(G,w,r)
Q = V[G]
// Fila de prioridade Q
foreach u  Q
// Inicialização
key[u] = 
key[r] = 0
[r] = NIL
while Q  
u = Extract_Min(Q)
foreach v  Adj[u]
if v  Q and w(u,v) < key[v]
[v] =u
key[v] = w(u,v) // Q é actualizada!
2003/2004
Análise e Síntese de Algoritmos
20
Algoritmo de Dijkstra — Complexidade
• Extract-Min e actualização de chaves na fila de
prioridade
– O(lg V) cada operação, em amontoado binário (binary heap)
• Extract-Min executado O(V) vezes
• Número de vezes que chaves são actualizadas é O(E)
– OBS: cada arco é analisado apenas uma vez,
independentemente do ciclo while exterior, e não causa mais
do que uma actualização do amontoado !
• Tempo de execução é: O((V+E) lg V)
– Se fila de prioridade utiliza um amontoado binário
2003/2004
Análise e Síntese de Algoritmos
21
Algoritmo de Dijkstra — Correcção
• Como resultado da aplicação do algoritmo de
Dijkstra, d[u] = (s,u) para u  V[G]
24.6
– Provar que d[u] = (s,u) quando u adicionado ao conjunto S,
e que a igualdade é posteriormente mantida
– Prova por contradição. Seja u o primeiro vértice tal que
quando u é adicionado ao conjunto S, d[u]  (s,u)
• u  s, porque d[s] = (s,s) = 0
• s  S, pelo que S   quando u adicionado a S
– Existe caminho de s para u (caso contrário, d[u] = (s,u) = ;
uma contradição)
• existe caminho mais curto p de s para u
• y: primeiro vértice de p em V-S
• x: predecessor de y, último vértice de p em S
2003/2004
Análise e Síntese de Algoritmos
22
Algoritmo de Dijkstra — Correcção
– Quando u é adicionado a S, d[y] = (s,y)
• x pertence a S
• d[x] = (s,x) (porque u é o primeiro vértice para o qual
igualdade não se verifica)
• Quando x adicionado a S, relaxação causa d[y] = (s,y),
24.14
porque caminho mais curto para y passa por x
– y aparece antes de u num caminho mais curto, pelo que (s,y) 
(s,u) (pesos não negativos)
24.11
• d[y] = (s,y)  (s,u)  d[u]
• Mas y e u em V-S, e u escolhido antes de y, pelo que d[u] 
d[y]
•  d[y] = (s,y) = (s,u) = d[u], o que contradiz escolha de u !
• Necessariamente, valor de d[u] mantém-se após d[u] = (s,u)
24.11
2003/2004
Análise e Síntese de Algoritmos
23
Algoritmo de Dijkstra — Condições
• Pesos dos arcos têm que ser não negativos:
6
s
1
u
v
3
w
-5
1
• Execução do algoritmo de Dijkstra:
– Analisar w (com d[w] = 3)
– Analisar v (com d[v] = 4)
– Analisar u (com d[u] = 6)
• Corrigir d[v] para 1
• Estimativa de w incorrecta (final=3; correcto=2) !
2003/2004
Análise e Síntese de Algoritmos
24
Algoritmo de Bellman-Ford —
Organização
• Permite pesos negativos e identifica existência de
ciclos negativos
• Baseado em sequência de passos de relaxação
• Apenas requer manutenção da estimativa associada
a cada vértice
2003/2004
Análise e Síntese de Algoritmos
25
Algoritmo de Bellman-Ford —
Pseudo-Código
(V E)
Bellman-Ford(G,w,s)
Initialize-Single-Source(G,s)
for i = 1 to |V[G]|-1
foreach (u,v)  E[G]
Relax(u,v,w)
foreach (u,v)  E[G]
if d[v] > d[u] + w(u,v)
// Ciclo negativo
return FALSE
// Sem ciclos negativos
return TRUE
• Exemplo
2003/2004
Análise e Síntese de Algoritmos
26
Algoritmo de Bellman-Ford —
Complexidade
• Por inspecção:
– Inicialização: (V)
– Ciclo for:
• Tempo de execução é (VE) devido aos dois ciclos, em V e
em E
– OBS: para cada i, todos os arcos de E são relaxados !
2003/2004
Análise e Síntese de Algoritmos
27
Algoritmo de Bellman-Ford —
Correcção
• Se G = (V,E) não contém ciclos negativos, então após a
24.2
aplicação do algoritmo de Bellman-Ford, d[v] = (s,v)
para todos os vértices atingíveis a partir de s
– Seja v atingível a partir de s, e seja p = vo,v1,…,vk um caminho
mais curto entre s e v, com v0 = s e vk = v
• p é simples, pelo que k  |V|-1
– Objectivo: provar por indução que para i = 0,1,…,k, d[vi] = (s,vi)
após iteração i sobre os arcos de G, e que valor não é alterado
posteriormente
24.11
• Base: d[v0] = (s,v0) = 0 após inicialização (e não se altera)
• Passo indutivo: assumir d[vi-1] = (s,vi-1) após iteração (i-1)
– Arco (vi-1,vi) relaxado na iteração i, pelo que d[vi] = (s,vi) após
iteração i (ver propriedades da relaxação) (e não se altera)
24.14
2003/2004
Análise e Síntese de Algoritmos
28
Algoritmo de Bellman-Ford —
Correcção
• Se G=(V,E) não contém ciclos negativos, o algoritmo de
24.4
Bellman-Ford retorna TRUE. Se o grafo contém algum
ciclo negativo atingível a partir de s, o algoritmo retorna
FALSE
– Sem ciclos negativos, resultado anterior assegura que para
qualquer arco (u,v) de E, d[v]  d[u] + w(u,v), pelo que teste do
algoritmo falha para todo o (u,v) e o valor retornado é TRUE
– Na presença de pelo menos um ciclo negativo atingível a partir
de s, c = vo,v1,…,vk, onde vo = vk
k
 w v i1, v i   0
i 1
– Prova por contradição. Admitir que algoritmo retorna TRUE
• Pelo que d[vi]  d[vi-1] + w(vi-1,vi), para i =1,…,k
2003/2004
Análise e Síntese de Algoritmos
29
Algoritmo de Bellman-Ford —
Correcção
– Somando desigualdades através do ciclo c:
k
k
k
i 1
i 1
i 1
 dv i    dv i1    wv i1, v i 
– Nota:
k
k
 dv i   dv i1 
i 1
i 1
Por ser um ciclo !
k
– Obtendo-se: 0   w v i1, v i 
i 1
– O que contradiz a hipótese de existência de um ciclo negativo
 algoritmo retorna FALSE.
2003/2004
Análise e Síntese de Algoritmos
30
Algoritmos de Dijkstra e Bellman-Ford
• Dijkstra:
– Só permite pesos não negativos
– Tempo de execuçao é O((V + E) lg V)
• Bellman-Ford
– Permite pesos negativos e identifica ciclos negativos
– Tempo de execução é (V E)
2003/2004
Análise e Síntese de Algoritmos
31
SSSPs em DAGs — Organização
DAG-Shortest-Paths(G,w,s)
Ordenação topológica dos vértices de G
Initialize-Single-Source(G,s)
foreach u  V[G] por ordem topológica
foreach v  Adj[u]
Relax(u,v,w)
• Tempo de execução: O(V+E)
• Exemplo
2003/2004
Análise e Síntese de Algoritmos
32
SSSPs em DAGs — Correcção
• Dado G = (V, E),dirigido, acíclico, como resultado do
24.5
algoritmo, d[v] = (s,v) para todo o v  V
– Se v não atíngivel de s, então d[v] = (s,v) = 
– Seja p = v0,v1,,vk um caminho mais curto, com v0 = s e vk = v
– Ordem topológica implica arcos analisados por ordem (v0, v1),
(v1, v2), …, (vk-1, vk)
24.11
• Cada arco é relaxado apenas uma vez
– Valor de d[v] não é alterado após d[v] = (s,v)
– Por indução, d[vi] = (s,vi) sempre que cada vértice vi é terminado
• Base: Estimativa de s não alterada; d[s] = d[v0] = (s,v0) = 0
• Indução: d[vi-1] = (s,vi-1) após terminar análise de vi-1
– Relaxação de (vi-1, vi) causa d[vi] = (s,vi), pelo que d[vi] = (s,vi)
após terminar análise de vi
24.14
2003/2004
Análise e Síntese de Algoritmos
33
Revisão
• Caminhos Mais Curtos com Fonte Única (SSSPs)
–
–
–
–
Definições e Propriedades
Algoritmo de Dijkstra
Algoritmo de Bellman-Ford
SSSPs em DAGs
• A seguir:
– Caminhos Mais Curtos entre Todos os Pares
2003/2004
Análise e Síntese de Algoritmos
(CLRS, Cap. 25)
34