Análise e Síntese de Algoritmos Caminhos Mais CurtosCLRS, Cap. 24

Análise e Síntese de Algoritmos

Caminhos Mais Curtos CLRS, Cap. 24

2003/2004 Análise e Síntese de Algoritmos 2

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


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


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:

• O peso do caminho mais curto de u para v é definido por:

• Um caminho mais curto de u para v é qualquer caminho p tal que w(p) = (u,v)

k

1ii1i v,vwpw

contrário caso

v para u de caminho existe sevu:pwminv,u

p


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


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) = -


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:

33

-5-2

s zx y

w(s,x,y,z) = 4w(s,x,y,x,y,z) = 2w(s,x,y,x,y,x,y,z) = 0

…


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):

sNILv:VvV

sVv:Ev,vE


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


Estudo dos SSSPs

• Sub-estrutura óptima: (sub-caminhos de caminhos mais curtos são caminhos mais curtos) – 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 !

24.1


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 (s,v) = w(p) = w(p’) + w(u,v) = (s,u) + w(u,v)

– 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)

24.10

24.1


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

– Algoritmos para SSSPs aplicam sequência de relaxações dos arcos de G após inicialização

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



• Propriedades da relaxação:

– 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

24.13




– 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)

– 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 !

24.11

24.10




– 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) +

w(u,v) = (s, v) • Mas, d[v] (s, v), pelo que d[v] = (s, v), e não se

altera !

24.14

24.1

24.11


Estudo dos SSSPs (Revisão)

– 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)

– Para todos os arcos (u,v) E verifica-se (s,v) (s,u) + w(u,v)

24.1

24.10


Estudo dos SSSPs (Revisão)


– 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)

– …

24.14

24.11

24.13


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


Algoritmo de Dijkstra — Pseudo-Código

• Exemplo

Dijkstra(G,w,s)Initialize-Single-Source(G,s)S = Q = V[G] // Fila de prioridade Qwhile Q

u = Extract_Min(Q)S = S {u}foreach v Adj[u]

Relax(u,v,w) // Actualizar Q

O(lg V)O(E)

O(V)

O(lg V)


Algoritmo de Dijkstra vs. Alg. de Prim

MST-Prim(G,w,r)Q = V[G] // Fila de prioridade Qforeach u Q // Inicialização

key[u] = key[r] = 0[r] = NILwhile Q

u = Extract_Min(Q)foreach v Adj[u]

if v Q and w(u,v) < key[v][v] =ukey[v] = w(u,v) // Q é actualizada!


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


Algoritmo de Dijkstra — Correcção

• Como resultado da aplicação do algoritmo de Dijkstra, d[u] = (s,u) para u V[G]– 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

24.6


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),

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)

• 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.14

24.11

24.11


Algoritmo de Dijkstra — Condições

• Pesos dos arcos têm que ser não negativos:

• 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) !

6

3 -5

s

v

u

w

1

1


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


Algoritmo de Bellman-Ford — Pseudo-Código

• Exemplo

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

(V E)


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 !


Algoritmo de Bellman-Ford — Correcção

• Se G = (V,E) não contém ciclos negativos, então após a 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

• 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.11

24.14

24.2



• Se G=(V,E) não contém ciclos negativos, o algoritmo de 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

– Prova por contradição. Admitir que algoritmo retorna TRUE

• Pelo que d[vi] d[vi-1] + w(vi-1,vi), para i =1,…,k

0v,vwk

1ii1i

24.4



– Somando desigualdades através do ciclo c:

– Nota:

– Obtendo-se:

– O que contradiz a hipótese de existência de um ciclo negativo

algoritmo retorna FALSE.

k

1i1i

k

1ii vdvd Por ser um ciclo !

k

1ii1i v,vw0

k

1ii1i

k

1i1i

k

1ii v,vwvdvd


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)


SSSPs em DAGs — Organização

• Tempo de execução: O(V+E)• Exemplo

DAG-Shortest-Paths(G,w,s)Ordenação topológica dos vértices de GInitialize-Single-Source(G,s)foreach u V[G] por ordem topológica

foreach v Adj[u]Relax(u,v,w)


SSSPs em DAGs — Correcção

• Dado G = (V, E),dirigido, acíclico, como resultado do 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)

• 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

24.11

24.5


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 (CLRS, Cap. 25)

Documents

Análise e Síntese de Algoritmos Caminhos Mais CurtosCLRS, Cap. 24