Denies Caminhos Mais Curtos com Fonte nica Algoritmo Dijkstra Algoritmo Bellman-Ford Caminhos mais curtos em DAGs

Anlise e Sntese de Algoritmos

Caminhos Mais Curtos com Fonte nica [CLRS, Cap. 24]
2010/2011
Denies Caminhos Mais Curtos com Fonte nica Algoritmo Dijkstra Algoritmo Bellman-Ford Caminhos mais curtos em DAGs
Contexto
Reviso [CLRS, Cap.1-13]
Fundamentos; notao; exemplos
Algoritmos em Grafos [CLRS, Cap.21-26]
Algoritmos elementares
rvores abrangentes
Caminhos mais curtos
Fluxos mximos
Programao Linear [CLRS, Cap.29]
Algoritmos e modelao de problemas com restries lineares
Tcnicas de Sntese de Algoritmos [CLRS, Cap.15-16]
Programao dinmica
Algoritmos greedy
Tpicos Adicionais [CLRS, Cap.32-35]
Emparelhamento de Cadeias de Caracteres
Complexidade Computacional
Algoritmos de Aproximao
Denies Caminhos Mais Curtos com Fonte nica Algoritmo Dijkstra Algoritmo Bellman-Ford Caminhos mais curtos em DAGs
Resumo
1
Denies
Caminhos Mais Curtos
2
Caminhos Mais Curtos com Fonte nica
Representao de Caminhos Mais Curtos
Propriedades dos Caminhos Mais Curtos
Operao de Relaxao
3
Algoritmo Dijkstra
4
Algoritmo Bellman-Ford
5
Caminhos mais curtos em DAGs
Denies Caminhos Mais Curtos com Fonte nica Algoritmo Dijkstra Algoritmo Bellman-Ford Caminhos mais curtos em DAGs
Caminhos Mais Curtos
Caminhos Mais Curtos
Denies
Dado um grafo G = (V, E), dirigido, com uma funo de pesos
w : E IR, dene-se o peso de um caminho p, onde
p =< v
0
, v
1
, . . . , v
k
>, como a soma dos pesos dos arcos que
compem p:
w(p) =
k

i =1
w(v
i 1
, v
i
)
O peso do caminho mais curto de u para v denido por:
(u, v) =

min {w(p) : u
p
v} se existe caminho de u para v
caso contrrio
Um caminho mais curto de u para v qualquer caminho p tal que
w(p) = (u, v)
Denies Caminhos Mais Curtos com Fonte nica Algoritmo Dijkstra Algoritmo Bellman-Ford Caminhos mais curtos em DAGs
Caminhos Mais Curtos
Caminhos Mais Curtos
Problemas de Caminhos Mais Curtos
Caminhos Mais Curtos com Fonte nica (SSSPs)
Identicar o caminho mais curto de um vrtice fonte s V para qualquer
outro vrtice v V
Denies Caminhos Mais Curtos com Fonte nica Algoritmo Dijkstra Algoritmo Bellman-Ford Caminhos mais curtos em DAGs
Caminhos Mais Curtos
Caminhos Mais Curtos
Problemas de Caminhos Mais Curtos
Caminhos Mais Curtos com Fonte nica (SSSPs)
Identicar o caminho mais curto de um vrtice fonte s V para qualquer
outro vrtice v V
Caminhos Mais Curtos com Destino nico
Identicar o caminho mais curto de qualquer vrtice v V para um vrtice
destino t V
Denies Caminhos Mais Curtos com Fonte nica Algoritmo Dijkstra Algoritmo Bellman-Ford Caminhos mais curtos em DAGs
Caminhos Mais Curtos
Caminhos Mais Curtos
Problemas de Caminhos Mais Curtos
Caminhos Mais Curtos com Fonte nica (SSSPs)
Identicar o caminho mais curto de um vrtice fonte s V para qualquer
outro vrtice v V
Caminhos Mais Curtos com Destino nico
Identicar o caminho mais curto de qualquer vrtice v V para um vrtice
destino t V
Caminho Mais Curto entre Par nico
Identicar caminho mais curto entre dois vrtices u e v
Denies Caminhos Mais Curtos com Fonte nica Algoritmo Dijkstra Algoritmo Bellman-Ford Caminhos mais curtos em DAGs
Caminhos Mais Curtos
Caminhos Mais Curtos
Problemas de Caminhos Mais Curtos
Caminhos Mais Curtos com Fonte nica (SSSPs)
Identicar o caminho mais curto de um vrtice fonte s V para qualquer
outro vrtice v V
Caminhos Mais Curtos com Destino nico
Identicar o caminho mais curto de qualquer vrtice v V para um vrtice
destino t V
Caminho Mais Curto entre Par nico
Identicar caminho mais curto entre dois vrtices u e v
Caminhos Mais Curtos entre Todos os Pares (APSPs)
Identicar um caminho mais curto entre cada par de vrtices de V
Denies Caminhos Mais Curtos com Fonte nica Algoritmo Dijkstra Algoritmo Bellman-Ford Caminhos mais curtos em DAGs
Caminhos Mais Curtos
Caminhos Mais Curtos
Ciclos Negativos
Arcos podem ter pesos com valor negativo
possvel a existncia de ciclos com peso total negativo
Se ciclo negativo no atingvel a partir da fonte s, ento (s, v) bem
denido
Se ciclo negativo atingvel a partir da fonte s, ento os pesos dos
caminhos mais curtos no so bem denidos
Neste caso, sempre possvel encontrar um caminho mais curto de s
para qualquer vrtice includo no ciclo e dene-se (s, v) =
Denies Caminhos Mais Curtos com Fonte nica Algoritmo Dijkstra Algoritmo Bellman-Ford Caminhos mais curtos em DAGs
Caminhos Mais Curtos
Caminhos Mais Curtos
Ciclos Negativos
Arcos podem ter pesos com valor negativo
possvel a existncia de ciclos com peso total negativo
Se ciclo negativo no atingvel a partir da fonte s, ento (s, v) bem
denido
Se ciclo negativo atingvel a partir da fonte s, ento os pesos dos
caminhos mais curtos no so bem denidos
Neste caso, sempre possvel encontrar um caminho mais curto de s
para qualquer vrtice includo no ciclo e dene-se (s, v) =
s x
y
z
3
2
-4
-2
w(< s, x, y, z >) = 3
w(< s, x, y, x, y, z >) = 1
w(< s, x, y, x, y, x, y, z >) =1
. . .
Denies Caminhos Mais Curtos com Fonte nica Algoritmo Dijkstra Algoritmo Bellman-Ford Caminhos mais curtos em DAGs
Caminhos Mais Curtos
Caminhos Mais Curtos
Identicao de Ciclos Negativos
Dijkstra: requer pesos no negativos
Bellman-Ford: identica ciclos negativos e reporta a sua existncia
Denies Caminhos Mais Curtos com Fonte nica Algoritmo Dijkstra Algoritmo Bellman-Ford Caminhos mais curtos em DAGs
Representao de Caminhos Mais Curtos
Caminhos Mais Curtos com Fonte nica
Representao de Caminhos Mais Curtos
Para cada vrtice v V associar predecessor [v]
Aps identicao dos caminhos mais curtos, [v] indica qual o vrtice
anterior a v num 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}}
Denies Caminhos Mais Curtos com Fonte nica Algoritmo Dijkstra Algoritmo Bellman-Ford Caminhos mais curtos em DAGs
Representao de Caminhos Mais Curtos
Caminhos Mais Curtos com Fonte nica
Representao de Caminhos Mais Curtos
Uma rvore de caminhos mais curtos um sub-grafo dirigido
G

= (V

, E

), V

V e E

E, tal que:
V

o conjunto de vrtices atingveis 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
Observaes:
Aps identicao dos caminhos mais curtos de G a partir de fonte s,
G

dado por G

= (V

, E

)
Dados os mesmos grafo G e vrtice fonte s, G

no necessariamente
nico
Denies Caminhos Mais Curtos com Fonte nica Algoritmo Dijkstra Algoritmo Bellman-Ford Caminhos mais curtos em DAGs
Propriedades dos Caminhos Mais Curtos
Propriedades dos Caminhos Mais Curtos
Sub-estrutura ptima
Sub-caminhos de caminhos mais curtos so caminhos mais curtos
Seja p =< v
1
, v
2
, . . . , v
k
> um caminho mais curto entre v
1
e v
k
, e seja
p
ij
=< v
i
, v
i +1
, . . . , v
j
> um sub-caminho de p entre v
i
e v
j
.
Ento p
ij
um caminho mais curto entre v
i
e v
j
Porqu? Se existisse caminho mais curto entre v
i
e v
j
ento seria possvel
construir caminho entre v
1
e v
k
mais curto do que p;
Contradio, dado que p um caminho mais curto entre v
1
e v
k
.
v
k
v
k-1
v
j
v
i
v
1
v
2
v
i+1
Denies Caminhos Mais Curtos com Fonte nica Algoritmo Dijkstra Algoritmo Bellman-Ford Caminhos mais curtos em DAGs
Propriedades dos Caminhos Mais Curtos
Propriedades dos Caminhos Mais Curtos
Sub-estrutura ptima
Sub-caminhos de caminhos mais curtos so caminhos mais curtos
Seja p =< v
1
, v
2
, . . . , v
k
> um caminho mais curto entre v
1
e v
k
, e seja
p
ij
=< v
i
, v
i +1
, . . . , v
j
> um sub-caminho de p entre v
i
e v
j
.
Ento p
ij
um caminho mais curto entre v
i
e v
j
Porqu? Se existisse caminho mais curto entre v
i
e v
j
ento seria possvel
construir caminho entre v
1
e v
k
mais curto do que p;
Contradio, dado que p um caminho mais curto entre v
1
e v
k
.
Peso de um Caminho Mais Curto
Seja p =< s, . . . , v > um caminho mais curto entre s e v, que pode ser
decomposto em p
su
=< s, . . . , u > e (u, v). Ento
(s, v) = (s, u) +w(u, v)
p
su
caminho mais curto entre s e u
(s, v) = w(p) = w(p
su
) +w(u, v) = (s, u) +w(u, v)
Denies Caminhos Mais Curtos com Fonte nica Algoritmo Dijkstra Algoritmo Bellman-Ford Caminhos mais curtos em DAGs
Propriedades dos Caminhos Mais Curtos
Propriedades dos Caminhos Mais Curtos
Relao caminho mais curto com arcos do grafo
Para todos os arcos (u, v) E verica-se (s, v) (s, u) +w(u, v)
Caminho mais curto de s para v no pode ter mais peso do que
qualquer outro caminho de s para v
Assim, peso do caminho mais curto de s para v no 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)
Denies Caminhos Mais Curtos com Fonte nica Algoritmo Dijkstra Algoritmo Bellman-Ford Caminhos mais curtos em DAGs
Operao de Relaxao
Operao de Relaxao
Operao de Relaxao
Operao bsica dos algoritmos para clculo dos caminhos mais curtos
com fonte nica.
d[v]: denota a estimativa do caminho mais curto de s para v; limite
superior no valor do peso do caminho mais curto;
Algoritmos aplicam sequncia de relaxaes dos arcos de G aps
inicializao para actualizar a estimativa do caminho mais curto
Initialize-Single-Source(G, s)
1 for each v V[G]
2 do d[v]
3 [v] NIL
4 d[s] 0
Relax(u, v, w)
1 if d[v] > d[u] +w(u, v)
2 then d[v] d[u] +w(u, v)
3 [v] u
Denies Caminhos Mais Curtos com Fonte nica Algoritmo Dijkstra Algoritmo Bellman-Ford Caminhos mais curtos em DAGs
Operao de Relaxao
Propriedades da Relaxao
Propriedades da Relaxao
Aps relaxar arco (u, v), temos que d[v] d[u] +w(u, v)
Se d[v] > d[u] +w(u, v) antes da relaxao, ento
d[v] = d[u] +w(u, v) aps relaxao
Se d[v] d[u] +w(u, v) antes da relaxao, ento
d[v] d[u] +w(u, v) aps relaxao
Em qualquer caso, d[v] d[u] +w(u, v) aps relaxao
u
1
d[v]=f
u
2
u
3
v
w(u
2
,v)=7
d[u
3
]=5
d[u
2
]=1
d[u
1
]=4
u
1
d[v]=8
u
2
u
3
v
w(u
2
,v)=7
d[u
3
]=5
d[u
2
]=1
d[u
1
]=4
u
1
d[v]=8
u
2
u
3
v
w(u
2
,v)=7
d[u
3
]=5
d[u
2
]=1
d[u
1
]=4
u
1
d[v]=7
u
2
u
3
v
w(u
2
,v)=7
d[u
3
]=5
d[u
2
]=1
d[u
1
]=4
Relax (u
1
,v,w) Relax (u
2
,v,w) Relax (u
3
,v,w)
Denies Caminhos Mais Curtos com Fonte nica Algoritmo Dijkstra Algoritmo Bellman-Ford Caminhos mais curtos em DAGs
Operao de Relaxao
Propriedades da Relaxao (2)
Propriedades da Relaxao
d[v] (s, v) para qualquer v V[G] e para qualquer sequncia de passos
de relaxao nos arcos de G. Se d[v] atinge o valor (s, v), ento o valor
no mais alterado
d[v] (s, v) vlido aps inicializao
Prova por contradio para os restantes casos:
Seja v o primeiro vrtice para o qual a relaxao do arco (u, v) causa
d[v] < (s, v)
Aps relaxar arco: d[u] +w(u, v) = d[v] < (s, v) (s, u) +w(u, v)
Pelo que, d[u] < (s, u) antes da relaxao de (u, v); Contradio, dado
que v seria o primeiro vrtice para o qual d[v] < (s, v)
Aps ter d[v] = (s, v), o valor de d[v] no pode decrescer; e pela
relaxao tambm no pode crescer!
Denies Caminhos Mais Curtos com Fonte nica Algoritmo Dijkstra Algoritmo Bellman-Ford Caminhos mais curtos em DAGs
Operao de Relaxao
Propriedades da Relaxao (3)
Propriedades da Relaxao
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), ento d[v] = (s, v) aps a chamada a Relax(u, v, w)
Se d[u] = (s, u) ento valor de d[u] no mais alterado
Aps relaxar arco (u, v):
d[v] d[u] +w(u, v) = (s, u) +w(u, v) = (s, v)
Mas, d[v] (s, v), pelo que d[v] = (s, v), e no se altera !
Denies Caminhos Mais Curtos com Fonte nica Algoritmo Dijkstra Algoritmo Bellman-Ford Caminhos mais curtos em DAGs
Operao de Relaxao
Resumo Propriedades Caminhos Mais Curtos
Sub-estrutura ptima
Sub-caminhos de caminhos mais curtos so caminhos mais curtos
Seja p =< v
1
, v
2
, . . . , v
k
> um caminho mais curto entre v
1
e v
k
, e seja
p
ij
=< v
i
, v
i +1
, . . . , v
j
> um sub-caminho de p entre v
i
e v
j
.
Ento p
ij
um caminho mais curto entre v
i
e v
j
Sub-estrutura ptima
Seja p =< s, . . . , v > um caminho mais curto entre s e v, que pode ser
decomposto em p
su
=< s, . . . , u > e (u, v). Ento (s, v) = (s, u) +w(u, v)
Relao caminho mais curto com arcos do grafo
Para todos os arcos (u, v) E verica-se (s, v) (s, u) +w(u, v)
Denies Caminhos Mais Curtos com Fonte nica Algoritmo Dijkstra Algoritmo Bellman-Ford Caminhos mais curtos em DAGs
Operao de Relaxao
Resumo Propriedades Operao Relaxao
Propriedades da Relaxao
Aps relaxar arco (u, v), temos que d[v] d[u] +w(u, v)
Propriedades da Relaxao (2)
d[v] (s, v) para qualquer v V[G] e para qualquer sequncia de passos
de relaxao nos arcos de G. Se d[v] atinge o valor (s, v), ento o valor
no mais alterado
Propriedades da Relaxao (3)
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), ento d[v] = (s, v) aps a chamada a Relax(u, v, w)
Denies Caminhos Mais Curtos com Fonte nica Algoritmo Dijkstra Algoritmo Bellman-Ford Caminhos mais curtos em DAGs
Algoritmo de Dijkstra
Organizao do Algoritmo
Todos os arcos com pesos no negativos
Algoritmo Greedy
Algoritmo mantm conjunto de vrtices S com pesos dos caminhos
mais curtos j calculados
A cada passo algoritmo selecciona vrtice u em V S com menor
estimativa do peso do caminho mais curto
vrtice u inserido em S
arcos que saem de u so relaxados
Denies Caminhos Mais Curtos com Fonte nica Algoritmo Dijkstra Algoritmo Bellman-Ford Caminhos mais curtos em DAGs
Algoritmo de Dijkstra
Dijkstra(G, w, s)
1 Initialize-Single-Source(G, s)
2 S / 0
3 Q V[G] Fila de Prioridade
4 while Q = / 0
5 do u Extract-Min(Q)
6 S S {u}
7 for each v Adj [u]
8 do Relax(u, v, w) Actualizao de Q
Denies Caminhos Mais Curtos com Fonte nica Algoritmo Dijkstra Algoritmo Bellman-Ford Caminhos mais curtos em DAGs
Algoritmo de Dijkstra: Exemplo
s
d[s]=0
u v
d[u]=f
S[u]=NIL
d[v]=f
S[v]=NIL
10
1
s
u
Q
s
d[s]=0
S[s]=NIL
y x
d[x]=f
S[x]=NIL
d[y]=f
S[y]=NIL
5
2
3 2
9
6 4
u
v
x
y
Denies Caminhos Mais Curtos com Fonte nica Algoritmo Dijkstra Algoritmo Bellman-Ford Caminhos mais curtos em DAGs
Algoritmo de Dijkstra: Exemplo
s
d[s]=0
u v
d[u]=10
S[u]=s
d[v]=f
S[v]=NIL
10
1
x
u
Q
s
d[s]=0
S[s]=NIL
y x
d[x]=5
S[x]=s
d[y]=f
S[y]=NIL
5
2
3 2
9
6 4
u
v
y
Denies Caminhos Mais Curtos com Fonte nica Algoritmo Dijkstra Algoritmo Bellman-Ford Caminhos mais curtos em DAGs
Algoritmo de Dijkstra: Exemplo
s
d[s]=0
u v
d[u]=8
S[u]=x
d[v]=14
S[v]=x
10
1
y
u
Q
s
d[s]=0
S[s]=NIL
y x
d[x]=5
S[x]=s
d[y]=7
S[y]=x
5
2
3 2
9
6 4
u
v
Denies Caminhos Mais Curtos com Fonte nica Algoritmo Dijkstra Algoritmo Bellman-Ford Caminhos mais curtos em DAGs
Algoritmo de Dijkstra: Exemplo
s
d[s]=0
u v
d[u]=8
S[u]=x
d[v]=13
S[v]=y
10
1
u
v
Q
s
d[s]=0
S[s]=NIL
y x
d[x]=5
S[x]=s
d[y]=7
S[y]=x
5
2
3 2
9
6 4
v
Denies Caminhos Mais Curtos com Fonte nica Algoritmo Dijkstra Algoritmo Bellman-Ford Caminhos mais curtos em DAGs
Algoritmo de Dijkstra: Exemplo
s
d[s]=0
u v
d[u]=8
S[u]=x
d[v]=9
S[v]=u
10
1
v
Q
s
d[s]=0
S[s]=NIL
y x
d[x]=5
S[x]=s
d[y]=7
S[y]=x
5
2
3 2
9
6 4
Denies Caminhos Mais Curtos com Fonte nica Algoritmo Dijkstra Algoritmo Bellman-Ford Caminhos mais curtos em DAGs
Algoritmo de Dijkstra: Exemplo
s
d[s]=0
u v
d[u]=8
S[u]=x
d[v]=9
S[v]=u
10
1
Q
1
s
d[s]=0
S[s]=NIL
y x
d[x]=5
S[x]=s
d[y]=7
S[y]=x
5
2
3 2
9
6 4
Denies Caminhos Mais Curtos com Fonte nica Algoritmo Dijkstra Algoritmo Bellman-Ford Caminhos mais curtos em DAGs
Algoritmo de Dijkstra
Complexidade
Estrutura muito semelhante ao Algoritmo de Prim para clculo de MST
Fila de prioridade baseada em amontoados (heap)
Quando um vrtice extrado da la Q, implica actualizao de Q
Cada vrtice extrado apenas 1 vez O(V)
Actualizao de Q: O(lg V)
Ento, O(V lg V)
Para cada arco (i.e. O(E)) operao de relaxao aplicada apenas 1
vez. Cada operao de relaxao pode implicar uma actualizao de Q
em O(lg V)
Complexidade algoritmo Dijkstra: O((V +E) lg V)
Denies Caminhos Mais Curtos com Fonte nica Algoritmo Dijkstra Algoritmo Bellman-Ford Caminhos mais curtos em DAGs
Algoritmo de Dijkstra
Correco do Algoritmo
Provar invariante do algoritmo: d[u] = (s, u) quando u adicionado ao
conjunto S, e que a igualdade posteriormente mantida
Prova por contradio. Assume-se que existe um primeiro vrtice u tal
que d[u] = (s, u) quando u adicionado a S
Necessariamente temos que u = s porque d[s] = (s, s) = 0
S = / 0 porque s S quando u adicionado a S
Tem que existir caminho mais curto de s para u, dado que caso
contrrio teriamos d[u] = (s, u) =
Denies Caminhos Mais Curtos com Fonte nica Algoritmo Dijkstra Algoritmo Bellman-Ford Caminhos mais curtos em DAGs
Algoritmo de Dijkstra
Correco do Algoritmo (2)
Pressuposto: u o primeiro vrtice tal que d[u] = (s, u) quando u
adicionado a S
Seja p =< s, . . . , x, y, . . . , u > o caminho mais curto de s para u
Tem que existir pelo menos um vrtice do caminho p que ainda no
esteja em S, caso contrrio, d[u] = (s, u) devido relaxao dos
arcos que compem o caminho p
Seja (x, y) um arco de p tal que x S e y S
Temos que d[x] = (s, x) porque x S e u o primeiro vrtice em que
isso no ocorre
Temos tambm que d[y] = (s, y) porque o arco (x, y) foi relaxado
quando x foi adicionado a S
Como y predecessor de u no caminho mais curto at u, ento
(s, y) (s, u), porque os pesos dos arcos so no-negativos
Mas se u adicionado a S antes de y, temos que d[u] d[y]. Logo,
d[u] (s, y) (s, u). O que contradiz o pressuposto de d[u] = (s, u).
Denies Caminhos Mais Curtos com Fonte nica Algoritmo Dijkstra Algoritmo Bellman-Ford Caminhos mais curtos em DAGs
Algoritmo de Dijkstra
Pesos Negativos no Grafo
Os pesos do grafo tm que ser no-negativos para garantir a correco do
algoritmo
Exemplo
s
w
u
v
6
3 -5
1
1
Execuo do Algoritmo Dijkstra:
- Analisar w com d[w] = 3
- Analisar v com d[v] = 4
- Analisar u com d[u] = 6
- No nal temos que d[w] = 3 = (s, w) = 2
Denies Caminhos Mais Curtos com Fonte nica Algoritmo Dijkstra Algoritmo Bellman-Ford Caminhos mais curtos em DAGs
Algoritmo de Bellman-Ford
Organizao do Algoritmo
Permite pesos negativos e identica existncia de ciclos negativos
Baseado em sequncia de passos de relaxao
Apenas requer manuteno da estimativa associada a cada vrtice
Denies Caminhos Mais Curtos com Fonte nica Algoritmo Dijkstra Algoritmo Bellman-Ford Caminhos mais curtos em DAGs
Algoritmo de Bellman-Ford
Bellman-Ford(G, w, s)
1 Initialize-Single-Source(G, s)
2 for i 1 to |V[G]| 1
3 do for each (u, v) E[G]
4 do Relax(u, v, w)
5 for each (u, v) E[G]
6 do if d[v] > d[u] +w(u, v)
7 then return FALSE Ciclo negativo
8 return TRUE Sem ciclos negativos
Denies Caminhos Mais Curtos com Fonte nica Algoritmo Dijkstra Algoritmo Bellman-Ford Caminhos mais curtos em DAGs
Algoritmo de Bellman-Ford: Exemplo
s
d[s]=0
u v
d[u]=10
S[u]=s
d[v]=f
S[v]=NIL
10
9
1
6
4
9
ordem de
relaxao
1 iterao
s
d[s]=0
S[s]=NIL
y x
d[x]=5
S[x]=s
d[y]=f
S[y]=NIL
5
2*
3 2
9
6 4
9
1
2*
3
2
10
5
Denies Caminhos Mais Curtos com Fonte nica Algoritmo Dijkstra Algoritmo Bellman-Ford Caminhos mais curtos em DAGs
Algoritmo de Bellman-Ford: Exemplo
s
d[s]=0
u v
d[u]=8
S[u]=x
d[v]=11
S[v]=u
10
9
1
6
4
9
ordem de
relaxao
2 iterao
s
d[s]=0
S[s]=NIL
y x
d[x]=5
S[x]=s
d[y]=7
S[y]=x
5
2*
3 2
9
6 4
9
1
2*
3
2
10
5
Denies Caminhos Mais Curtos com Fonte nica Algoritmo Dijkstra Algoritmo Bellman-Ford Caminhos mais curtos em DAGs
Algoritmo de Bellman-Ford: Exemplo
s
d[s]=0
u v
d[u]=8
S[u]=x
d[v]=9
S[v]=u
10
9
1
6
4
9
ordem de
relaxao
3 iterao
s
d[s]=0
S[s]=NIL
y x
d[x]=5
S[x]=s
d[y]=7
S[y]=x
5
2*
3 2
9
6 4
9
1
2*
3
2
10
5
Denies Caminhos Mais Curtos com Fonte nica Algoritmo Dijkstra Algoritmo Bellman-Ford Caminhos mais curtos em DAGs
Algoritmo de Bellman-Ford: Outro exemplo
s
d[s]=0
u v
d[u]=8
S[u]=x
d[v]=9
S[v]=u
10
9
1
10
5
2
ordem de
relaxao
1 iterao
s
d[s]=0
S[s]=NIL
y x
d[x]=5
S[x]=s
d[y]=7
S[y]=x
5
2*
3 2
9
6 4
2
3
1
2*
9
4
6
Denies Caminhos Mais Curtos com Fonte nica Algoritmo Dijkstra Algoritmo Bellman-Ford Caminhos mais curtos em DAGs
Algoritmo de Bellman-Ford: Outro exemplo
ordem de relaxao
ordem de relaxao
melhor
caso
pior
caso caso
Denies Caminhos Mais Curtos com Fonte nica Algoritmo Dijkstra Algoritmo Bellman-Ford Caminhos mais curtos em DAGs
Algoritmo de Bellman-Ford
Complexidade
Inicializao: (V)
A complexidade do ciclo for O(VE) devido aos dois ciclos, em V e
em E.
Em cada iterao todos os arcos so relaxados
Complexidade algoritmo Bellman-Ford: O(VE)
Denies Caminhos Mais Curtos com Fonte nica Algoritmo Dijkstra Algoritmo Bellman-Ford Caminhos mais curtos em DAGs
Algoritmo de Bellman-Ford
Correco
Se G = (V, E) no contm ciclos negativos, ento aps a aplicao do
algoritmo de Bellman-Ford, d[v] = (s, v) para todos os vrtices atingveis a
partir de s
Seja v atingvel a partir de s, e seja p =< v
0
, v
1
, . . . , v
k
> um caminho
mais curto entre s e v, com v
0
= s e v
k
= v
p simples, pelo que k |V| 1
Prova: provar por induo que d[v
i
] = (s, v
i
) para i = 0, 1, . . . , k, aps
iterao i sobre os arcos de G, e que valor no alterado
posteriormente
Base: d[v
0
] = (s, v
0
) = 0 aps inicializao (e no se altera)
Passo indutivo: assumir d[v
i 1
] = (s, v
i 1
) aps iterao (i-1)
Arco (v
i 1
, v
i
) relaxado na iterao i , pelo que d[v
i
] = (s, v
i
) aps
iterao i (e no se altera)
Denies Caminhos Mais Curtos com Fonte nica Algoritmo Dijkstra Algoritmo Bellman-Ford Caminhos mais curtos em DAGs
Algoritmo de Bellman-Ford
Correco (2)
Se G = (V, E) no contm ciclos negativos, o algoritmo de Bellman-Ford
retorna TRUE. Se o grafo contm algum ciclo negativo atingvel a partir de s,
o algoritmo retorna FALSE
Se no existem ciclos negativos, resultado anterior assegura que para
qualquer arco (u, v) E, d[v] d[u] +w(u, v), pelo que teste do
algoritmo falha para todo o (u, v) e o valor retornado TRUE
Caso contrrio, na presena de pelo menos um ciclo negativo atingvel
a partir de s, c =< v
0
, v
1
, . . . , v
k
>, onde v
0
= v
k
, temos que

k
i =1
w(v
i 1
, v
i
) < 0
Denies Caminhos Mais Curtos com Fonte nica Algoritmo Dijkstra Algoritmo Bellman-Ford Caminhos mais curtos em DAGs
Algoritmo de Bellman-Ford
Correco (3)
Se G = (V, E) no contm ciclos negativos, o algoritmo de Bellman-Ford
retorna TRUE. Se o grafo contm algum ciclo negativo atingvel a partir de s,
o algoritmo retorna FALSE
Prova por contradio. Admitir que algoritmo retorna TRUE na presena
de ciclo negativo. Pelo que d[v
i
] d[v
i 1
] +w(v
i 1
, v
i
), para
i = 1, . . . , k
Somando as desigualdades ao longo do ciclo temos que:
k

i =1
d[v
i
]
k

i =1
d[v
i 1
] +
k

i =1
w(v
i 1
, v
i
)
Note-se que

k
i =1
d[v
i
] =

k
i =1
d[v
i 1
] por ser um ciclo
Temos ento que

k
i =1
w(v
i 1
, v
i
) > 0, o que contradiz a existncia de
um ciclo negativo. Logo, o algoritmo retorna FALSE
Denies Caminhos Mais Curtos com Fonte nica Algoritmo Dijkstra Algoritmo Bellman-Ford Caminhos mais curtos em DAGs
Caminhos mais curtos em DAGs
DAG-Shortest-Path(G, w, s)
1 Ordenao topolgica dos vrtices de G
2 Initialize-Single-Source(G, s)
3 for each u V[G] por ordem topolgica
4 do for each v Adj [u]
5 do Relax(u, v, w)
Complexidade:
Denies Caminhos Mais Curtos com Fonte nica Algoritmo Dijkstra Algoritmo Bellman-Ford Caminhos mais curtos em DAGs
Caminhos mais curtos em DAGs
DAG-Shortest-Path(G, w, s)
1 Ordenao topolgica dos vrtices de G
2 Initialize-Single-Source(G, s)
3 for each u V[G] por ordem topolgica
4 do for each v Adj [u]
5 do Relax(u, v, w)
Complexidade: O(V +E)
Denies Caminhos Mais Curtos com Fonte nica Algoritmo Dijkstra Algoritmo Bellman-Ford Caminhos mais curtos em DAGs
Caminhos mais curtos em DAGs
Correco
Dado G = (V, E), dirigido, acclico, como resultado do algoritmo, temos que
d[v] = (s, v) para todo o v V
Seja v atingvel a partir de s, e seja p =< v
0
, v
1
, . . . , v
k
> um caminho
mais curto entre s e v, com v
0
= s e v
k
= v
Ordenao topolgica implica que analisados por ordem (v
0
, v
1
),
(v
1
, v
2
), . . ., (v
k1
, v
k
)
Prova por induo: d[v
i
] = (s, v
i
) sempre que cada vrtice v
i

terminado
Base: Estimativa de s no alterada aps inicializao;
d[s] = d[v
0
] = (s, v
0
) = 0
Induo: d[v
i 1
] = (s, v
i 1
) aps terminar anlise de v
i 1
Relaxao do arco (v
i 1
, v
i
) causa d[v
i
] = (s, v
i
), pelo que
d[v
i
] = (s, v
i
) aps terminar anlise de v
i
Denies Caminhos Mais Curtos com Fonte nica Algoritmo Dijkstra Algoritmo Bellman-Ford Caminhos mais curtos em DAGs
Caminhos mais curtos em DAGs
Resumo
Algoritmo Dijkstra
S permite pesos no negativos
Complexidade: O((V +E) lg V)
Algoritmo Bellman-Ford
Permite pesos negativos e identica ciclos negativos
Complexidade: O(VE)
Caminhos mais curtos em DAGs
Grafos aciclicos. Podemos fazer ordenao topolgica dos vrtices
Complexidade: O(V +E)