Algoritmos de Dijkstra e Bellman-Fordbf.pdf · 2020. 4. 27. · 1 Algoritmos de Dijkstra e Bellman-Ford Prof. CelsoA.W.Santos J702 :: Teoria de Grafos [email protected]

1

Algoritmos de Dijkstra eBellman-Ford

Prof. Celso A. W. Santos

J702 :: Teoria de Grafos

[email protected]

24/04/2020

2

Mais avisos...

� Avaliações serão realizadas por listas de exercícios, disponibilizadasem meu site todas as sextas-feiras.

. Prazo de entrega: até a quinta-feira da semana seguinte, às 23h59m

. Submissão deve ser feita em formato PDF

. Enviar com assunto no e-mail:[J702 - Lista X] Matrícula XXXXXXX ← tudo maiúsculo!

Exemplo: [J702 - Lista 3] Matrícula D648H12

. Sim... eu vou zerar estudos submetidos fora do padrão :)

� Todas as listas deverão ser entregues presencialmente ao retorno dasatividades!

Se você não tem impressora...

� As notas das Listas 2 e 3 estarão disponíveis no site na sexta-feiraque vem, dia 01/05.

http://ccsiswift.pro.br/celso.santos


2

Mais avisos...












2

Mais avisos...












2

Mais avisos...












2

Mais avisos...












2

Mais avisos...












2

Mais avisos...












3

Na aula passada...

4

Grafos ponderados

Definição. Um grafo ponderado é uma tripla G = (V,U,w) tal que V éum conjunto de vértices, E é um conjunto de arestas, e w : E → R éuma função peso que atribui um valor real a cada aresta do grafo.

s

b

c

d

e

f

g

t

4

3

2 3

5 5

6

1

5

23

7

4

5

Caminho Mínimo

Caminho MínimoEntrada: Um grafo ponderado G = (V,U,w), um vértice fonte s ∈ V eum vértice destino t ∈ V .Pergunta: Qual é o menor caminho entre s e t? E qual é o seu custo?

s

b

c

d

e

f

g

t

4

3

2 3

5 5

6

1

5

23

7

4

5

Caminho Mínimo


s

b

c

d

e

f

g

t

4

3

23

5 5

6

1

5

23

7

4

5

Caminho Mínimo


s

b

c

d

e

f

g

t

4

3

23

5 5

6

1

5

23

7

4

COMO ENCONTRAR O MENOR CAMINHO?

6

Algoritmos

Algoritmos para resolver Caminho Mínimo

� Algoritmo de Dijkstra. Single-source. Dados vértices s, t ∈ V , encontra o menor caminho entre s e t.. Tem um problema!

� Algoritmo de Bellman-Ford. Single-source. “Resolve” o problema!

� Algoritmo de Floyd-Warshall. All-pairs. Mais rápido que executar Single-source para todos os vértices

6

Algoritmos





6

Algoritmos





6

Algoritmos





6

Algoritmos





6

Algoritmos





6

Algoritmos





6

Algoritmos





6

Algoritmos





6

Algoritmos





6

Algoritmos





7

Algoritmo de Dijkstra

8


Inicializa-Single-Source(G, s):

para todo vértice v ∈ V :d[v] =∞;π[v] =⊥;

d[s] = 0;

Relaxa(u, v, w):se d[v] > d[u] + w(u, v):

d[v] = d[u] + w(u, v);π[v] = u;

Dijkstra(G, s):Inicializa-Single-Source(G, s)S = ∅;Q = V ;enquanto Q 6= ∅ faça:

u = Extrai-Min(Q);S = S ∪ {u};p/ todo vértice v ∈ N(u) faça:

Relaxa(u, v, w);

8




d[s] = 0;


d[v] = d[u] + w(u, v);π[v] = u;



Relaxa(u, v, w);

8




d[s] = 0;


d[v] = d[u] + w(u, v);π[v] = u;



Relaxa(u, v, w);

9

Exemplo de Execução :: Algoritmo de Dijkstra

d

s b c d e f g t

π

s b c d e f g t

s

b

c

d

e

f

g

t

4

3

2 3

5 5

6

1

5

23

7

4

9


d 0

s

∞b

∞

c

∞d

∞

e

∞

f

∞

g

∞t

π ⊥

s

⊥

b

⊥

c

⊥

d

⊥

e

⊥

f

⊥

g

⊥

t

s

b

c

d

e

f

g

t

4

3

2 3

5 5

6

1

5

23

7

4

9


d 0

s

∞b

∞

c

∞d

∞

e

∞

f

∞

g

∞t

π ⊥

s

⊥

b

⊥

c

⊥

d

⊥

e

⊥

f

⊥

g

⊥

t

s

b

c

d

e

f

g

t

4

3

2 3

5 5

6

1

5

23

7

4

9


d 0

s

4

b

∞

c

∞d

∞

e

∞

f

∞

g

∞t

π ⊥

s

s

b

⊥

c

⊥

d

⊥

e

⊥

f

⊥

g

⊥

t

s

b

c

d

e

f

g

t

4

3

2 3

5 5

6

1

5

23

7

4

9


d 0

s

4

b

3

c

∞d

∞

e

∞

f

∞

g

∞t

π ⊥

s

s

b

s

c

⊥

d

⊥

e

⊥

f

⊥

g

⊥

t

s

b

c

d

e

f

g

t

4

3

2 3

5 5

6

1

5

23

7

4

9


d 0

s

4

b

3

c

∞d

∞

e

∞

f

∞

g

∞t

π ⊥

s

s

b

s

c

⊥

d

⊥

e

⊥

f

⊥

g

⊥

t

s

b

c

d

e

f

g

t

4

3

2 3

5 5

6

1

5

23

7

4

9


d 0

s

4

b

3

c

∞d

∞

e

∞

f

∞

g

∞t

π ⊥

s

s

b

s

c

⊥

d

⊥

e

⊥

f

⊥

g

⊥

t

s

b

c

d

e

f

g

t

4

3

2 3

5 5

6

1

5

23

7

4

9


d 0

s

4

b

3

c

6

d

∞

e

∞

f

∞

g

∞t

π ⊥

s

s

b

s

c

c

d

⊥

e

⊥

f

⊥

g

⊥

t

s

b

c

d

e

f

g

t

4

3

2 3

5 5

6

1

5

23

7

4

9


d 0

s

4

b

3

c

6

d

9

e

∞

f

∞

g

∞t

π ⊥

s

s

b

s

c

c

d

c

e

⊥

f

⊥

g

⊥

t

s

b

c

d

e

f

g

t

4

3

2 3

5 5

6

1

5

23

7

4

9


d 0

s

4

b

3

c

6

d

9

e

∞

f

∞

g

∞t

π ⊥

s

s

b

s

c

c

d

c

e

⊥

f

⊥

g

⊥

t

s

b

c

d

e

f

g

t

4

3

2 3

5 5

6

1

5

23

7

4

9


d 0

s

4

b

3

c

6

d

9

e

∞

f

∞

g

∞t

π ⊥

s

s

b

s

c

c

d

c

e

⊥

f

⊥

g

⊥

t

s

b

c

d

e

f

g

t

4

3

2 3

5 5

6

1

5

23

7

4

9


d 0

s

4

b

3

c

6

d

9

e

∞

f

∞

g

∞t

π ⊥

s

s

b

s

c

c

d

c

e

⊥

f

⊥

g

⊥

t

s

b

c

d

e

f

g

t

4

3

2 3

5 5

6

1

5

23

7

4

9


d 0

s

4

b

3

c

6

d

9

e

∞

f

∞

g

∞t

π ⊥

s

s

b

s

c

c

d

c

e

⊥

f

⊥

g

⊥

t

s

b

c

d

e

f

g

t

4

3

2 3

5 5

6

1

5

23

7

4

9


d 0

s

4

b

3

c

6

d

7

e

∞

f

∞

g

∞t

π ⊥

s

s

b

s

c

c

d

d

e

⊥

f

⊥

g

⊥

t

s

b

c

d

e

f

g

t

4

3

2 3

5 5

6

1

5

23

7

4

9


d 0

s

4

b

3

c

6

d

7

e

11

f

∞

g

∞t

π ⊥

s

s

b

s

c

c

d

d

e

d

f

⊥

g

⊥

t

s

b

c

d

e

f

g

t

4

3

2 3

5 5

6

1

5

23

7

4

9


d 0

s

4

b

3

c

6

d

7

e

11

f

9

g

∞t

π ⊥

s

s

b

s

c

c

d

d

e

d

f

d

g

⊥

t

s

b

c

d

e

f

g

t

4

3

2 3

5 5

6

1

5

23

7

4

9


d 0

s

4

b

3

c

6

d

7

e

11

f

9

g

∞t

π ⊥

s

s

b

s

c

c

d

d

e

d

f

d

g

⊥

t

s

b

c

d

e

f

g

t

4

3

2 3

5 5

6

1

5

23

7

4

9


d 0

s

4

b

3

c

6

d

7

e

11

f

9

g

∞t

π ⊥

s

s

b

s

c

c

d

d

e

d

f

d

g

⊥

t

s

b

c

d

e

f

g

t

4

3

2 3

5 5

6

1

5

23

7

4

9


d 0

s

4

b

3

c

6

d

7

e

11

f

9

g

∞t

π ⊥

s

s

b

s

c

c

d

d

e

d

f

d

g

⊥

t

s

b

c

d

e

f

g

t

4

3

2 3

5 5

6

1

5

23

7

4

9


d 0

s

4

b

3

c

6

d

7

e

11

f

9

g

∞t

π ⊥

s

s

b

s

c

c

d

d

e

d

f

d

g

⊥

t

s

b

c

d

e

f

g

t

4

3

2 3

5 5

6

1

5

23

7

4

9


d 0

s

4

b

3

c

6

d

7

e

11

f

9

g

13

t

π ⊥

s

s

b

s

c

c

d

d

e

d

f

d

g

g

t

s

b

c

d

e

f

g

t

4

3

2 3

5 5

6

1

5

23

7

4

9


d 0

s

4

b

3

c

6

d

7

e

11

f

9

g

13

t

π ⊥

s

s

b

s

c

c

d

d

e

d

f

d

g

g

t

s

b

c

d

e

f

g

t

4

3

2 3

5 5

6

1

5

23

7

4

9


d 0

s

4

b

3

c

6

d

7

e

11

f

9

g

13

t

π ⊥

s

s

b

s

c

c

d

d

e

d

f

d

g

g

t

s

b

c

d

e

f

g

t

4

3

2 3

5 5

6

1

5

23

7

4

9


d 0

s

4

b

3

c

6

d

7

e

11

f

9

g

13

t

π ⊥

s

s

b

s

c

c

d

d

e

d

f

d

g

g

t

s

b

c

d

e

f

g

t

4

3

2 3

5 5

6

1

5

23

7

4

9


d 0

s

4

b

3

c

6

d

7

e

11

f

9

g

13

t

π ⊥

s

s

b

s

c

c

d

d

e

d

f

d

g

g

t

s

b

c

d

e

f

g

t

4

3

2 3

5 5

6

1

5

23

7

4

9


d 0

s

4

b

3

c

6

d

7

e

11

f

9

g

13

t

π ⊥

s

s

b

s

c

c

d

d

e

d

f

d

g

g

t

s

b

c

d

e

f

g

t

4

3

2 3

5 5

6

1

5

23

7

4

9


d 0

s

4

b

3

c

6

d

7

e

11

f

9

g

13

t

π ⊥

s

s

b

s

c

c

d

d

e

d

f

d

g

g

t

s

b

c

d

e

f

g

t

4

3

2 3

5 5

6

1

5

23

7

4

COMO ENCONTRAR O MENOR CAMINHO?

9


d 0

s

4

b

3

c

6

d

7

e

11

f

9

g

13

t

π ⊥

s

s

b

s

c

c

d

d

e

d

f

d

g

g

t

s

b

c

d

e

f

g

t

4

3

2 3

5 5

6

1

5

23

7

4

9


d 0

s

4

b

3

c

6

d

7

e

11

f

9

g

13

t

π ⊥

s

s

b

s

c

c

d

d

e

d

f

d

g

g

t

s

b

c

d

e

f

g

t

4

3

2 3

5 5

6

1

5

23

7

4

9


d 0

s

4

b

3

c

6

d

7

e

11

f

9

g

13

t

π ⊥

s

s

b

s

c

c

d

d

e

d

f

d

g

g

t

s

b

c

d

e

f

g

t

4

3

2 3

5 5

6

1

5

23

7

4

9


d 0

s

4

b

3

c

6

d

7

e

11

f

9

g

13

t

π ⊥

s

s

b

s

c

c

d

d

e

d

f

d

g

g

t

s

b

c

d

e

f

g

t

4

3

23

5 5

6

1

5

23

7

4

9


d 0

s

4

b

3

c

6

d

7

e

11

f

9

g

13

t

π ⊥

s

s

b

s

c

c

d

d

e

d

f

d

g

g

t

s

b

c

d

e

f

g

t

4

3

23

5 5

6

1

5

23

7

4

9


d 0

s

4

b

3

c

6

d

7

e

11

f

9

g

13

t

π ⊥

s

s

b

s

c

c

d

d

e

d

f

d

g

g

t

s

b

c

d

e

f

g

t

4

3

23

5 5

6

1

5

23

7

4

E QUAL É O SEU CUSTO?

9


d 0

s

4

b

3

c

6

d

7

e

11

f

9

g

13

t

π ⊥

s

s

b

s

c

c

d

d

e

d

f

d

g

g

t

s

b

c

d

e

f

g

t

4

3

23

5 5

6

1

5

23

7

4

10

Encontrando a Resposta

Devolve-Menor-Caminho(G, s):Dijkstra(G, s);imprime “Custo: ” + d[t];imprime “Caminho: t ← ”v = π[t];enquanto v 6= ⊥ faça:

imprime: “v ←”;v = π[v];

11

O problema do Dijkstra: Ciclos Negativos

� O algoritmo de Dijkstra funciona mesmo quando existem pesosnegativos nas arestas.

s

b

c

d

e

f

g

t

4

3

2 3

5 5

6

1

5

23

7

4

� ... mas quebra quando existem ciclos negativos!

11



s

b

c

d

e

f

g

t

-4

3

2 -3

5 5

6

1

5

-23

7

4


11



s

b

c

d

e

f

g

t

-4

3

2 -3

5 5

6

1

5

-23

7

4


11



s

b

c

d

e

f

g

t

-9

3

2 -3

5 5

6

1

5

-23

7

4


11



s

b

c

d

e

f

g

t

-9

3

2 -3

5 5

6

1

5

-23

-7

4


12

O Algoritmo de Bellman-Ford

13

Algoritmo de Bellman-Ford

Bellman-Ford(G, s):Inicializa-Single-Source(G, s);de i = 1 até n− 1 faça:

para toda aresta uv ∈ E faça:Relaxa(u, v, w);

para toda aresta uv ∈ E faça:se d[v] > d[u] + w(u, v) então:

devolve Falsedevolve True

14

Exemplo de Execução :: Algoritmo de Bellman-Ford

d

s b c d e

π

s b c d e

s

b

c

d

e

4

3

-2 3

5

6

-1

14


d 0

s

∞b

∞

c

∞d

∞

e

π ⊥

s

⊥

b

⊥

c

⊥

d

⊥

e

s

b

c

d

e

4

3

-2 3

5

6

-1

14


d 0

s

∞b

∞

c

∞d

∞

e

π ⊥

s

⊥

b

⊥

c

⊥

d

⊥

e

Ordem das Arestas:1a : de2a : bd3a : sc4a : bc5a : sb6a : cd7a : ce

s

b

c

d

e

4

3

-2 3

5

6

-1

14


d 0

s

∞b

∞

c

∞d

∞

e

π ⊥

s

⊥

b

⊥

c

⊥

d

⊥

e


s

b

c

d

e

4

3

-2 3

5

6

-1

14


d 0

s

∞b

∞

c

∞d

∞

e

π ⊥

s

⊥

b

⊥

c

⊥

d

⊥

e


s

b

c

d

e

4

3

-2 3

5

6

-1

14


d 0

s

∞b

∞

c

∞d

∞

e

π ⊥

s

⊥

b

⊥

c

⊥

d

⊥

e


s

b

c

d

e

4

3

-2 3

5

6

-1

14


d 0

s

∞b

3

c

∞d

∞

e

π ⊥

s

⊥

b

s

c

⊥

d

⊥

e


s

b

c

d

e

4

3

-2 3

5

6

-1

14


d 0

s

∞b

3

c

∞d

∞

e

π ⊥

s

⊥

b

s

c

⊥

d

⊥

e


s

b

c

d

e

4

3

-2 3

5

6

-1

14


d 0

s

∞b

3

c

∞d

∞

e

π ⊥

s

⊥

b

s

c

⊥

d

⊥

e


s

b

c

d

e

4

3

-2 3

5

6

-1

14


d 0

s

4

b

3

c

∞d

∞

e

π ⊥

s

s

b

s

c

⊥

d

⊥

e


s

b

c

d

e

4

3

-2 3

5

6

-1

14


d 0

s

4

b

3

c

∞d

∞

e

π ⊥

s

s

b

s

c

⊥

d

⊥

e


s

b

c

d

e

4

3

-2 3

5

6

-1

14


d 0

s

4

b

3

c

6

d

∞

e

π ⊥

s

s

b

s

c

c

d

⊥

e


s

b

c

d

e

4

3

-2 3

5

6

-1

14


d 0

s

4

b

3

c

6

d

∞

e

π ⊥

s

s

b

s

c

c

d

⊥

e


s

b

c

d

e

4

3

-2 3

5

6

-1

14


d 0

s

4

b

3

c

6

d

9

e

π ⊥

s

s

b

s

c

c

d

c

e


s

b

c

d

e

4

3

-2 3

5

6

-1

14


d 0

s

4

b

3

c

6

d

9

e

π ⊥

s

s

b

s

c

c

d

c

e


s

b

c

d

e

4

3

-2 3

5

6

-1

ACABOU O ALGORITMO?

14


d 0

s

4

b

3

c

6

d

9

e

π ⊥

s

s

b

s

c

c

d

c

e


s

b

c

d

e

4

3

-2 3

5

6

-1

14


d 0

s

4

b

3

c

6

d

5

e

π ⊥

s

s

b

s

c

c

d

d

e


s

b

c

d

e

4

3

-2 3

5

6

-1

14


d 0

s

4

b

3

c

6

d

5

e

π ⊥

s

s

b

s

c

c

d

d

e


s

b

c

d

e

4

3

-2 3

5

6

-1

14


d 0

s

4

b

3

c

6

d

5

e

π ⊥

s

s

b

s

c

c

d

d

e


s

b

c

d

e

4

3

-2 3

5

6

-1

14


d 0

s

4

b

3

c

6

d

5

e

π ⊥

s

s

b

s

c

c

d

d

e


s

b

c

d

e

4

3

-2 3

5

6

-1

14


d 0

s

4

b

2

c

6

d

5

e

π ⊥

s

s

b

b

c

c

d

d

e


s

b

c

d

e

4

3

-2 3

5

6

-1

14


d 0

s

4

b

2

c

6

d

5

e

π ⊥

s

s

b

b

c

c

d

d

e


s

b

c

d

e

4

3

-2 3

5

6

-1

14


d 0

s

4

b

2

c

6

d

5

e

π ⊥

s

s

b

b

c

c

d

d

e


s

b

c

d

e

4

3

-2 3

5

6

-1

14


d 0

s

4

b

2

c

5

d

5

e

π ⊥

s

s

b

b

c

c

d

d

e


s

b

c

d

e

4

3

-2 3

5

6

-1

14


d 0

s

4

b

2

c

5

d

5

e

π ⊥

s

s

b

b

c

c

d

d

e


s

b

c

d

e

4

3

-2 3

5

6

-1

14


d 0

s

4

b

2

c

5

d

5

e

π ⊥

s

s

b

b

c

c

d

d

e


s

b

c

d

e

4

3

-2 3

5

6

-1

ACABOU O ALGORITMO?

14


d 0

s

4

b

2

c

5

d

5

e

π ⊥

s

s

b

b

c

c

d

d

e


s

b

c

d

e

4

3

-2 3

5

6

-1

14


d 0

s

4

b

2

c

5

d

5

e

π ⊥

s

s

b

b

c

c

d

d

e


s

b

c

d

e

4

3

-2 3

5

6

-1

14


d 0

s

4

b

2

c

5

d

5

e

π ⊥

s

s

b

b

c

c

d

d

e


s

b

c

d

e

4

3

-2 3

5

6

-1

ACABOU O ALGORITMO?

14


d 0

s

4

b

2

c

5

d

5

e

π ⊥

s

s

b

b

c

c

d

d

e


s

b

c

d

e

4

3

-2 3

5

6

-1

ACABOU O ALGORITMO?

15

Exemplo de Execução (Ruim) :: Algoritmo de Bellman-Ford

d 0

a

∞b

∞

c

π ⊥

a

⊥

b

⊥

c

Ordem das Arestas:1a : bc2a : ca3a : ab

a

b

c

4

3

-8

15


d 0

a

4

b

∞

c

π ⊥

a

s

b

⊥

c


a

b

c

4

3

-8

15


d −1

a

4

b

−4

c

π c

a

s

b

b

c


a

b

c

4

3

-8

15


d −1

a

4

b

−4

c

π c

a

s

b

b

c


a

b

c

4

3

-8

ACABOU O ALGORITMO?

15


d −1

a

4

b

−4

c

π c

a

s

b

b

c


a

b

c

4

3

-8

15


d −1

a

4

b

−4

c

π c

a

s

b

b

c


a

b

c

4

3

-8

15


d −1

a

4

b

−4

c

π c

a

s

b

b

c


a

b

c

4

3

-8

15


d −1

a

4

b

−4

c

π c

a

s

b

b

c


a

b

c

4

3

-8

15


d −1

a

4

b

−4

c

π c

a

s

b

b

c


a

b

c

4

3

-8

d[b] > d[a] + w(a, b)!

15


d −1

a

4

b

−4

c

π c

a

s

b

b

c


a

b

c

4

3

-8

Algoritmo devolve False!!

16

Comparando os Algoritmos


� Algoritmo de Dijkstra. Single-source. Complexidade: O(n log n + m)

� Algoritmo de Bellman-Ford. Single-source. Complexidade: O(nm)

� Algoritmo de Floyd-Warshall. All-pairs. Complexidade: O(n3)

16






16






16






16






16






16






16






16






16






17

Dúvidas?

18

Aula que vem...

19

Árvore Geradora Mínima

v1

v2

v3

v4 v5

v6

v7v8

30

18

25

23

15

28

17

33

2122

3227

31 35

19

Árvore Geradora MínimaEntrada: Um grafo ponderado G = (V,U,w).Pergunta: Qual é a árvore T ⊆ G de custo mínimo que gera G?

19

Árvore Geradora Mínima

v1

v2

v3

v4 v5

v6

v7v8

30

18

25

23

15

28

17

33

2122

3227

31 35

19

Árvore Geradora MínimaEntrada: Um grafo ponderado G = (V,U,w).Pergunta: Qual é a árvore T ⊆ G de custo mínimo que gera G?

Documents

Algoritmos de Dijkstra e Bellman-Fordbf.pdf · 2020. 4. 27. · 1 Algoritmos de Dijkstra e Bellman-Ford Prof. CelsoA.W.Santos J702 :: Teoria de Grafos [email protected]