53
Projeto e Análise de Algoritmos Método Guloso Altigran Soares da Silva Universidade Federal do Amazonas Departamento de Ciência da Computação

Projeto e Análise de Algoritmos Método Guloso · Projeto e Análise de Algoritmos Método Guloso Altigran Soares da Silva ... Algoritmo baseado em vértices ! Constrói uma árvore

Embed Size (px)

Citation preview

Page 1: Projeto e Análise de Algoritmos Método Guloso · Projeto e Análise de Algoritmos Método Guloso Altigran Soares da Silva ... Algoritmo baseado em vértices ! Constrói uma árvore

Projeto e Análise de Algoritmos

Método Guloso Altigran Soares da Silva

Universidade Federal do Amazonas

Departamento de Ciência da Computação

Page 2: Projeto e Análise de Algoritmos Método Guloso · Projeto e Análise de Algoritmos Método Guloso Altigran Soares da Silva ... Algoritmo baseado em vértices ! Constrói uma árvore

2

Árvore Geradora

n  Um árvore geradora de um grafo G é um subgrafo de G que n  é uma árvore n  Contém todos os vértices de G

Árvore geradora de G

Page 3: Projeto e Análise de Algoritmos Método Guloso · Projeto e Análise de Algoritmos Método Guloso Altigran Soares da Silva ... Algoritmo baseado em vértices ! Constrói uma árvore

3

Árvore geradora mínima

n  Seja G = (V,E) um grafo conexo e não dirigido

n  Seja uma função de custo W: E → R que atribui um custo a cada aresta de G

( , )( ) ( , )

u v Tw T w u v

= ∑

n  Árvore geradora: Uma árvore que conecta todos os vértices

n  Árvores geradora Mínima: árvore geradora que minimiza:

Page 4: Projeto e Análise de Algoritmos Método Guloso · Projeto e Análise de Algoritmos Método Guloso Altigran Soares da Silva ... Algoritmo baseado em vértices ! Constrói uma árvore

4

Sub-estrutura ótima

n  AEM T

n  Removendo algum arco (u,v) particiona T em T1 e T2

n  Como n  T1 é uma AEM de G1=(V1,E1) n  T2 é uma AEM de G2=(V2,E2)

1 2( ) ( , ) ( ) ( )w T w u v w T w T= + +

T1

T2

Page 5: Projeto e Análise de Algoritmos Método Guloso · Projeto e Análise de Algoritmos Método Guloso Altigran Soares da Silva ... Algoritmo baseado em vértices ! Constrói uma árvore

5

Escolha Gulosa

n  Propriedade: n  Escolhas localmente ótimas ou gulosas

(greedy) levam á uma solução global ótima

n  Teorema n  Seja G=(V, E), e seja S ⊆ V n  Seja (u,v) a aresta de menor custo em G que

conecta S a V – S n  Então (u,v) ∈ a alguma AEM de G

Page 6: Projeto e Análise de Algoritmos Método Guloso · Projeto e Análise de Algoritmos Método Guloso Altigran Soares da Silva ... Algoritmo baseado em vértices ! Constrói uma árvore

6

Escolha Gulosa (2)

u v

x y

S V-S

Page 7: Projeto e Análise de Algoritmos Método Guloso · Projeto e Análise de Algoritmos Método Guloso Altigran Soares da Silva ... Algoritmo baseado em vértices ! Constrói uma árvore

7

Escolha Gulosa (3)

n  Prova n  Suponha (u,v) ∉ T n  Mesmo assim, u e v devem estar em T e deve haver

um caminho de u até v emT n  Seja qualquer aresta (x, y) neste caminho que cruza

de S paraV – S n  Como (u,v) tem o menor custo, então w(u,v) ≤ w(x,y) n  Assim, a árvore que inclui (x,y) não pode ter o custo

menor que árvore que inclui (u,v) e portanto ela não é mínima.

Page 8: Projeto e Análise de Algoritmos Método Guloso · Projeto e Análise de Algoritmos Método Guloso Altigran Soares da Silva ... Algoritmo baseado em vértices ! Constrói uma árvore

8

Algoritmo Genérico para AEM

AEM(G,w) 1 A←∅ // Conterá os arcos da AEM 2 enquanto A não formar uma AEM faça 3 Encontre um arco (u,v) seguro para A 4 A←A∪{(u,v)} 5 retorne A

Arco seguro – arco que garante que A: n  forma uma árvore n  inclui os arcos mínimos

Page 9: Projeto e Análise de Algoritmos Método Guloso · Projeto e Análise de Algoritmos Método Guloso Altigran Soares da Silva ... Algoritmo baseado em vértices ! Constrói uma árvore

9

Alg. Genérico para AEM (2)

AEM2(G, w) 1 A←∅ // Conterá as arestas da AEM 2 enquanto A não for uma árvore geradora faça 3.1 Faça um corte(S, V-S) em G que respeita A 3.2 Seja (u,v) a aresta mínima entre S e V-S 4 A←A∪{(u,v)} 5 retorne A

Page 10: Projeto e Análise de Algoritmos Método Guloso · Projeto e Análise de Algoritmos Método Guloso Altigran Soares da Silva ... Algoritmo baseado em vértices ! Constrói uma árvore

10

Algoritmo de Prim

n  Algoritmo baseado em vértices n  Constrói uma árvore T, com um vértice de cada

vez. n  Utiliza um conjunto de vértices que corresponde

a porção de T que já foi computada n  Rotula os vertices que estão fora deste

conjunto com n  key[v] – arco de menor custo que conecta v a um

vértice no conjunto n  key[v] = ∞, se não existe tal arco

Page 11: Projeto e Análise de Algoritmos Método Guloso · Projeto e Análise de Algoritmos Método Guloso Altigran Soares da Silva ... Algoritmo baseado em vértices ! Constrói uma árvore

11

Algoritmo de Prim (2) Prim(G,w,r) 01 Q ← V[G] // Q – vertices que formarão T 02 para cada u ∈ Q 03 key[u] ← ∞04 key[r] ← 0 05 π[r] ← NIL 06 enquanto Q ≠ ∅ faça07 u ← ExtráiMin(Q) 08 para cada v ∈ Adj[u] do 09 se v ∈ Q e w(u,v) < key[v] então 10 π[v] ← u 11 key[v] ← w(u,v)

Page 12: Projeto e Análise de Algoritmos Método Guloso · Projeto e Análise de Algoritmos Método Guloso Altigran Soares da Silva ... Algoritmo baseado em vértices ! Constrói uma árvore

12

Prim(G,w,r) 01 Q ← V[G] // Q – vertices que formarão T 02 para cada u ∈ Q 03 key[u] ← ∞04 key[r] ← 0 05 π[r] ← NIL 06 enquanto Q ≠ ∅ faça07 u ← ExtráiMin(Q) 08 para cada v ∈ Adj[u] do 09 se v ∈ Q e w(u,v) < key[v] então 10 π[v] ← u 11 key[v] ← w(u,v)

Algoritmo de Prim (3)

Atualiza

key[v]

Page 13: Projeto e Análise de Algoritmos Método Guloso · Projeto e Análise de Algoritmos Método Guloso Altigran Soares da Silva ... Algoritmo baseado em vértices ! Constrói uma árvore

13

O(V) vezes

O(E) arestas

O(log V)

Algoritmo de Prim (4) O(V)

O(log V)

O(1)

Prim(G,w,r) 01 Q ← V[G] // Q – vertices que formarão T 02 para cada u ∈ Q 03 key[u] ← ∞04 key[r] ← 0 05 π[r] ← NIL 06 enquanto Q ≠ ∅ faça07 u ← ExtráiMin(Q) 08 para cada v ∈ Adj[u] do 09 se v ∈ Q e w(u,v) < key[v] então 10 π[v] ← u 11 key[v] ← w(u,v)

Page 14: Projeto e Análise de Algoritmos Método Guloso · Projeto e Análise de Algoritmos Método Guloso Altigran Soares da Silva ... Algoritmo baseado em vértices ! Constrói uma árvore

14

Prim: exemplo

Page 15: Projeto e Análise de Algoritmos Método Guloso · Projeto e Análise de Algoritmos Método Guloso Altigran Soares da Silva ... Algoritmo baseado em vértices ! Constrói uma árvore

15

Prim: exemplo (2)

Page 16: Projeto e Análise de Algoritmos Método Guloso · Projeto e Análise de Algoritmos Método Guloso Altigran Soares da Silva ... Algoritmo baseado em vértices ! Constrói uma árvore

16

Prim: exemplo (3)

Page 17: Projeto e Análise de Algoritmos Método Guloso · Projeto e Análise de Algoritmos Método Guloso Altigran Soares da Silva ... Algoritmo baseado em vértices ! Constrói uma árvore

17

Filas de Prioridade

n  Uma fila de prioridades (FP) é uma ED que mantém um conjunto S de elementos, cada um associado a uma chave (key).

n  Uma FP deve suportar as seguintes operações: n  ConstróiFP(S): Carrega a FP com os elementos de S n  ExtráiMin(S): retorna e remoce o elemento de S que

tem a menor chave n  Atualiza(S,x,novachave): muda a chave do elemento

x n  Um heap binário pode ser usado

n  ConstróiFP – O(n) n  ExtraíMin e Atualiza – O(lg n)

Page 18: Projeto e Análise de Algoritmos Método Guloso · Projeto e Análise de Algoritmos Método Guloso Altigran Soares da Silva ... Algoritmo baseado em vértices ! Constrói uma árvore

18

Prim: Tempo de Execução

n  |V |.T (ExtráiMin) + O (E ).T (Atualiza) n  O (V lgV + E lgV) = O (E lgV )

Fila T(ExtráiMin) T(Atualiza) Total

array O (V ) O (1) O(V 2)

Heap binário O (lg V) O(lg V) O(E lgV )

Heap de Fibonacci O(lg V) O(1) O(V lgV +E )

Page 19: Projeto e Análise de Algoritmos Método Guloso · Projeto e Análise de Algoritmos Método Guloso Altigran Soares da Silva ... Algoritmo baseado em vértices ! Constrói uma árvore

19

Algoritmo de Kruskal

n  Algoritmo baseado em arcos n  Adiciona um arco de cada vez na ordem

crescente dos custos n  Mantém uma floresta A. n  Um arco é incluido se ele conecta vértices

de árvores distintas de A.

Page 20: Projeto e Análise de Algoritmos Método Guloso · Projeto e Análise de Algoritmos Método Guloso Altigran Soares da Silva ... Algoritmo baseado em vértices ! Constrói uma árvore

20

Algoritmo de Kruskal (2)

Kruskal(G,w) /* G=(V,E) */ 01 A ← ∅ 02 para cada vértice v ∈ V[G] do 03 Constrói-Conjunto({v})04 Ordenar as arestas de acordo com o custo w 05 para cada arco (u,v) nesta ordem faça 06 se Conjunto_de(u) ≠ Conjunto_de(v) então 07 A ← A ∪ {(u,v)} 08 União(Conjunto_de(u),Conjunto_de(v)) 09 retorne A

Page 21: Projeto e Análise de Algoritmos Método Guloso · Projeto e Análise de Algoritmos Método Guloso Altigran Soares da Silva ... Algoritmo baseado em vértices ! Constrói uma árvore

21

Exemplo – Kruskal

Page 22: Projeto e Análise de Algoritmos Método Guloso · Projeto e Análise de Algoritmos Método Guloso Altigran Soares da Silva ... Algoritmo baseado em vértices ! Constrói uma árvore

22

Exemplo – Kruskal (2)

Page 23: Projeto e Análise de Algoritmos Método Guloso · Projeto e Análise de Algoritmos Método Guloso Altigran Soares da Silva ... Algoritmo baseado em vértices ! Constrói uma árvore

23

Exemplo – Kruskal (3)

Page 24: Projeto e Análise de Algoritmos Método Guloso · Projeto e Análise de Algoritmos Método Guloso Altigran Soares da Silva ... Algoritmo baseado em vértices ! Constrói uma árvore

24

Exemplo – Kruskal (4)

Page 25: Projeto e Análise de Algoritmos Método Guloso · Projeto e Análise de Algoritmos Método Guloso Altigran Soares da Silva ... Algoritmo baseado em vértices ! Constrói uma árvore

25

Implementação de Conjuntos

n  Para implementar Kruskall é necessário utilizar uma lista de dados para manter conjuntos disjuntos de vértices

n  Operações n  Constrói_Conjunto(x): S ← {x} n  União(Si,Sj): S ← S – {Si,Sj} ∪ {Si ∪ Sj} n  Conjunto_de(x): retorna Si, tal que x ∈ Si

Page 26: Projeto e Análise de Algoritmos Método Guloso · Projeto e Análise de Algoritmos Método Guloso Altigran Soares da Silva ... Algoritmo baseado em vértices ! Constrói uma árvore

26

Conjuntos disjuntos como listas

n  Cada conjunto – lista de elementos identificados pelo primeiro elemento.

n  Todos os elementos na lista apontam para o primeiro elemento

n  União – adiciona a lista menor à lista maior n  Conjunto-de: O(1), União(u,v): O(min{|C(u)|, C(v)})

1 2 3 A B C ∅

4 ∅

1 2 3 A B C ∅

4

Page 27: Projeto e Análise de Algoritmos Método Guloso · Projeto e Análise de Algoritmos Método Guloso Altigran Soares da Silva ... Algoritmo baseado em vértices ! Constrói uma árvore

27

Kruskal: Tempo de Execução

n  Inicialização: O(V) n  Θ(E lg E) ~ Θ(E lg V) n  O(E) chamadas para Conjunto_De n  Custo de uniões

n  Seja t(v) o número de vezes em que um vértice v é movido para um novo conjunto maior

n  Cada vez que é um vértice é movido, o novo conjunto tem seu tamanho pelo menos dobrado: t(v) ≤ log V

n  Tempo total de união n  Tempo total: O(E lg V)

( ) logv Vt v V V

≤∑

Page 28: Projeto e Análise de Algoritmos Método Guloso · Projeto e Análise de Algoritmos Método Guloso Altigran Soares da Silva ... Algoritmo baseado em vértices ! Constrói uma árvore

28

Caminhos Mínimos

Page 29: Projeto e Análise de Algoritmos Método Guloso · Projeto e Análise de Algoritmos Método Guloso Altigran Soares da Silva ... Algoritmo baseado em vértices ! Constrói uma árvore

29

Caminho Mínimo

n  Seja um digrafo (grafo dirigido) G = (V,E) com uma função de custo W: E → R

n  O custo do caminho p = v1 → v2 → … → vk é

n  Caminho mínimo: caminho de menor custo

1

11

( ) ( , )k

i ii

w p w v v−

+=

=∑

Page 30: Projeto e Análise de Algoritmos Método Guloso · Projeto e Análise de Algoritmos Método Guloso Altigran Soares da Silva ... Algoritmo baseado em vértices ! Constrói uma árvore

30

Caminhos Mínimos

n  Problemas de caminho mínimo n  Fonte Única (Destino Único). Encontrar o

caminho mínimo de um dado vértice (fonte) para todos os outros vértices.

n  Par Único. Dados dois vértices, achar o menor caminho entre eles. A solução para o problema de fonte única server para este problema.

n  Todos os Pares. Encontrar o caminho mínimo entre todos os pares de vértices do grafo. A solução é um problema de programação dinâmica.

Page 31: Projeto e Análise de Algoritmos Método Guloso · Projeto e Análise de Algoritmos Método Guloso Altigran Soares da Silva ... Algoritmo baseado em vértices ! Constrói uma árvore

31

Sub-estrutura ótima

n  Teorema: os sub-caminhos de um caminho mínimo são caminhos mínimos

n  Prova (cut and paste) n  Se algum sub-caminho não fosse mínimo, ele

poderia ser substituído por um menor que levaria ao caminho mínimo total.

Page 32: Projeto e Análise de Algoritmos Método Guloso · Projeto e Análise de Algoritmos Método Guloso Altigran Soares da Silva ... Algoritmo baseado em vértices ! Constrói uma árvore

32

Inequação de triângulos

n  Definição n  d(u,v) ≡ custo cam. min. entre u e v

n  Teorema n  d(u,v) ≤ d(u,x) + d(x,v) para qq x

n  Prova n  o cam. min. entre u-v não pode ser maior que

nenhum outro caminho entre u-v, em particular o caminho que concatena os caminhos mínimos entre u-x e x-v

Page 33: Projeto e Análise de Algoritmos Método Guloso · Projeto e Análise de Algoritmos Método Guloso Altigran Soares da Silva ... Algoritmo baseado em vértices ! Constrói uma árvore

33

Pesos negativos e ciclos

n  Em geral, caminhos mínimos não podem ter ciclos, pois se tivessem os custo poderia ser reduzido removendo o ciclo.

n  Qualquer caminho mínimo em um grafo não pode ter mais que n – 1 arestas, onde n é o nr. de vértices

n  Arestas com pesos negativos podem ser consideradas no caminho mínimo, no entanto, neste caso, ciclos poderiam levar a caminhos de custo arbitrariamente menores

Page 34: Projeto e Análise de Algoritmos Método Guloso · Projeto e Análise de Algoritmos Método Guloso Altigran Soares da Silva ... Algoritmo baseado em vértices ! Constrói uma árvore

34

Relaxamento

n  Para cada vértice no grafo, é mantido um valor d[v], uma estimativa do custo total do camin. Este valor é inicializado como ∞

n  Relaxar um arco (u,v) consiste em testar se é possível melhorar o camin corrente para v passando por u

5

u v

v u

2

2

9

5 7

Relax(u,v)

5

u v

v u

2

2

6

5 6

Relax(u,v)

Relax (u,v,w) if d[v]>d[u]+w(u,v)then d[v] ← d[u]+w(u,v)

π[v] ← u

Page 35: Projeto e Análise de Algoritmos Método Guloso · Projeto e Análise de Algoritmos Método Guloso Altigran Soares da Silva ... Algoritmo baseado em vértices ! Constrói uma árvore

35

Algoritmo de Dijkstra

n  Arestas com pesos não negativos n  Algoritmo guloso

n  Similar à busca em largura (BFS)

n  Usa uma fila de prioridade Q usando d[v] como chave

n  Idéia básica n  Mantêm um conjunto S de vértices já processados

n  A cada passo, seleciona o vértice u mais próximo, inclui o vértice u, adiciona-o a S e relaxa todos os arcos que saem de u.

Page 36: Projeto e Análise de Algoritmos Método Guloso · Projeto e Análise de Algoritmos Método Guloso Altigran Soares da Silva ... Algoritmo baseado em vértices ! Constrói uma árvore

36

Dijkstra(G,w,s) 01 para cada v ∈ V

02 d[v] ← ∞

03 d[s]← 0

04 S ← ∅

05 Q ← V 06 enquanto Q ≠ ∅ faça 07 u ← ExtráiMin(Q)

08 S ← S ∪ {u}

09 para cada v ∈ Adj[u] faça 10 se d[v] > d[u]+w(u,v) então 11 d[v] ← d[u]+w(u,v)

Dijkstra Q : Fila de Prioridade que contém os vértices e tem d[v] como chave

Q = {(v1,d[v1]), (v2,d[v2]),..., (vV,d[vV])}

Retira o u de menor d[u] de Q

Conjunto de vértices já processados

Relaxamento

Page 37: Projeto e Análise de Algoritmos Método Guloso · Projeto e Análise de Algoritmos Método Guloso Altigran Soares da Silva ... Algoritmo baseado em vértices ! Constrói uma árvore

37

Dijkstra: Exemplo

∞ ∞

∞ ∞

0s

u v

y x

10

5

1

2 3 9 4 6 7

2

10 ∞

5 ∞

0s

u v

y x

10

5

1

2 3 9 4 6 7

2

u v

8 14

5 7

0s

y x

10

5

1

2 3 9 4 6 7

2

8 13

5 7

0s

u v

y x

10

5

1

2 3 9 4 6 7

2

Page 38: Projeto e Análise de Algoritmos Método Guloso · Projeto e Análise de Algoritmos Método Guloso Altigran Soares da Silva ... Algoritmo baseado em vértices ! Constrói uma árvore

38

Dijkstra: Exemplo

8 9

5 7

0

u v

y x

10

5

1

2 3 9 4 6 7

2

8 9

5 7

0

u v

y x

10

5

1

2 3 9 4 6 7

2

Page 39: Projeto e Análise de Algoritmos Método Guloso · Projeto e Análise de Algoritmos Método Guloso Altigran Soares da Silva ... Algoritmo baseado em vértices ! Constrói uma árvore

39

Dijkstra: Corretude

n  Provar que sempre que u é adicionado a S temos d [u] = δ(s,u), ou seja, d é mínimo, e que isto se mantêm daí em diante

n  Prova n  Temos que: ∀v, d [v] ≥ δ(s,v) n  Seja u o primeiro vértice escolhido tal que existe um

caminho mais curto até u ou seja d[u] > δ(s,u) n  Mostraremos que isso leva a uma contradição

Page 40: Projeto e Análise de Algoritmos Método Guloso · Projeto e Análise de Algoritmos Método Guloso Altigran Soares da Silva ... Algoritmo baseado em vértices ! Constrói uma árvore

40

Dijkstra: Corretude (2)

n  Seja y o primeiro vértice em V – S que pertence ao caminho mínimo verdadeiro de s até u.

n  Então d [y] = δ(s,y), pois: n  Para o predecessor x de y, onde x ∈S , d [x] é

minimo, já que u é o primeiro vértice incorreto n  Além disso, quando x é inserido em S, a aresta (x,y)

foi relaxada, assinalando a d[y] o valor correto.

Page 41: Projeto e Análise de Algoritmos Método Guloso · Projeto e Análise de Algoritmos Método Guloso Altigran Soares da Silva ... Algoritmo baseado em vértices ! Constrói uma árvore

41

Dijkstra: Corretude (3)

Primeiro vértice escolhido tal que

d[u] não é mínimo Vértice que está no caminho mínimo

“real” até u

Vértice corretamente

escolhido

Page 42: Projeto e Análise de Algoritmos Método Guloso · Projeto e Análise de Algoritmos Método Guloso Altigran Soares da Silva ... Algoritmo baseado em vértices ! Constrói uma árvore

42

Dijkstra: Corretude (4)

n  Assim: n  d[u] > δ(s,u) * Hipótese inicial n  > δ(s,y)+δ(y,u) * Sub-estrutura ótima n  > d [y]+δ(y,u) * Corretude de d [y] n  d[u] > d [y] * Pesos não negativos

n  Mas se d [u] > d [y] o algoritmo teria escolhido y ao invés de u da fila Q ⇒ contradição

n  Portanto d[u] = δ(s,u) no momento da inserção de u em S.

Page 43: Projeto e Análise de Algoritmos Método Guloso · Projeto e Análise de Algoritmos Método Guloso Altigran Soares da Silva ... Algoritmo baseado em vértices ! Constrói uma árvore

Dijkstra: Tempo de Execução

n  Implementação usando um heap binário n  Extract-Min: Cada chamada é O(lg V) n  d[v] ←d[u]+w(u,v)

n  Altera o Heap : O(lg V) n  No total são feitas |E | chamadas

n  Temos n  O(V) + O(V) + V O(lg V) + E O (lg v) n  V O(lg V) + E O (lg v) = O((V+E) lg v)

n  Se todos os vértices são alcançáveis da n  O(E lg v)

43

Page 44: Projeto e Análise de Algoritmos Método Guloso · Projeto e Análise de Algoritmos Método Guloso Altigran Soares da Silva ... Algoritmo baseado em vértices ! Constrói uma árvore

44

Dijkstra: Tempo de Execução

O(V)

O(V)

O(E) arestas

O(V) vezes

O(log V)

O(log V)

Dijkstra(G,w,s) 01 para cada v ∈ V

02 d[v] ← ∞

03 d[s]← 0

04 S ← ∅

05 Q ← V 06 enquanto Q ≠ ∅ faça 07 u ← ExtráiMin(Q)

08 S ← S ∪ {u}

09 para cada v ∈ Adj[u] faça 10 se d[v] > d[u]+w(u,v) então 11 d[v] ← d[u]+w(u,v)

Page 45: Projeto e Análise de Algoritmos Método Guloso · Projeto e Análise de Algoritmos Método Guloso Altigran Soares da Silva ... Algoritmo baseado em vértices ! Constrói uma árvore

45

Algoritmo de Bellman-Ford

n  Dijkstra não funciona com arestas negativas n  Não se pode assumir que o custo dos

caminhos só podem aumentar.

n  O Algortimo de Bellman-Ford detecta ciclos negativos ou retorna os caminhos mínimos.

Page 46: Projeto e Análise de Algoritmos Método Guloso · Projeto e Análise de Algoritmos Método Guloso Altigran Soares da Silva ... Algoritmo baseado em vértices ! Constrói uma árvore

46

Bellman-Ford

Bellman-Ford(G,w,s) 01 para cada v ∈ V[G] 02 d[v] ← ∞

03 d[s] ← 0

04 π[r] ← NIL

05 para i ← 1 até |V[G]|-1 faça06 para cada aresta (u,v) ∈ E[G] faça 07 Relax (u,v,w) 08 para cada aresta (u,v) ∈ E[G] faça 09 se d[v] > d[u] + w(u,v) então retorne falso 10 retorne verdadeiro

Relax (u,v,w) if d[v]>d[u]+w(u,v)then d[v] ← d[u]+w(u,v)

π[v] ← u

Page 47: Projeto e Análise de Algoritmos Método Guloso · Projeto e Análise de Algoritmos Método Guloso Altigran Soares da Silva ... Algoritmo baseado em vértices ! Constrói uma árvore

47

Bellman-Ford: Exemplo 5

∞ ∞

∞ ∞

0s

z y

6

7

8 -3

7 2

9

-2 x t

-4

6 ∞

7 ∞

0s

z y

6

7

8 -3

7 2

9

-2 x t

-4

6 4

7 2

0s

z y

6

7

8 -3

7 2

9

-2 x t

-4

2 4

7 2

0s

z y

6

7

8 -3

7 2

9

-2 x t

-4

5

5 5

Page 48: Projeto e Análise de Algoritmos Método Guloso · Projeto e Análise de Algoritmos Método Guloso Altigran Soares da Silva ... Algoritmo baseado em vértices ! Constrói uma árvore

48

Bellman-Ford: Exemplo

2 4

7 -2

0s

z y

6

7

8 -3

7 2

9

-2 x t

-4

5

Page 49: Projeto e Análise de Algoritmos Método Guloso · Projeto e Análise de Algoritmos Método Guloso Altigran Soares da Silva ... Algoritmo baseado em vértices ! Constrói uma árvore

49

Bellman-Ford: Tempo

Bellman-Ford(G,w,s) 01 para cada v ∈ V[G] 02 d[v] ← ∞

03 d[s] ← 0

04 π[r] ← NIL

05 para i ← 1 até |V[G]|-1 faça06 para cada aresta (u,v) ∈ E[G] faça 07 Relax (u,v,w) 08 para cada vértice (u,v) ∈ E[G] faça 09 se d[v] > d[u] + w(u,v) então retorne falso 10 retorne verdadeiro

(|V|-1)|E| + |E| = Θ(VE)

Page 50: Projeto e Análise de Algoritmos Método Guloso · Projeto e Análise de Algoritmos Método Guloso Altigran Soares da Silva ... Algoritmo baseado em vértices ! Constrói uma árvore

50

Bellman-Ford: Corretude

n  Provar que se o menor caminho entre s e u tem i arestas, então depois do i-ésimo passo do algoritmo teremos o menor caminho, ou seja, d[u]=δ(s,u)

n  Seja δi(s,u) o custo do caminho de s até u que é o mínimo entre todos os caminhos que contém no máximo i arestas

Page 51: Projeto e Análise de Algoritmos Método Guloso · Projeto e Análise de Algoritmos Método Guloso Altigran Soares da Silva ... Algoritmo baseado em vértices ! Constrói uma árvore

51

Bellman-Ford: Corretude (2)

n  Provar por indução que d[u]= δi(s,u) depois da i-ésima iteração n  Base da indução. Inicio do algoritmo n  Hipótese da indução: d[u] = δi-1(s,u) n  Passo indutivo

n  Caso 1: δi(s,u) = δi-1(s,u) => d[u]= δi(s,u) n  Caso 2: δi(s,u) = δi-1(s,z) + w(z,u)

n  Na iteração da arco é relaxado, inclusive (z,u), então d[u] = δi(s,u)

Page 52: Projeto e Análise de Algoritmos Método Guloso · Projeto e Análise de Algoritmos Método Guloso Altigran Soares da Silva ... Algoritmo baseado em vértices ! Constrói uma árvore

52

Belman-Ford: Corretude (3)

n  Se |V|=n, temos que depois de n-1 iterações: d[u] = δn-1(s,u), para cada vértice u.

n  Se ainda existe alguma aresta a relaxar no grafo então ainda existe um vértice u tal que δn(s,u) < δn-1(s,u).

n  Mas só existem n vértices. Portanto deve haver um ciclo, ele deve ser negativo.

n  Caso contrário, d[u]= δn-1(s,u) = δ(s,u), para todo u, uma vez que qualquer caminho mínimo terá nó máximo n-1 arestas.

Page 53: Projeto e Análise de Algoritmos Método Guloso · Projeto e Análise de Algoritmos Método Guloso Altigran Soares da Silva ... Algoritmo baseado em vértices ! Constrói uma árvore

Problema da Mochila

n  É necessário preencher uma mochila com objetos de diferentes pesos e valores. O objetivo é que se preencha a mochila com o maior valor possível, não ultrapassando o peso máximo.

53