dijkstra-bf

Prévia do material em texto

1
Algoritmos de Dijkstra e
Bellman-Ford
Prof. Celso A. W. Santos
J702 :: Teoria de Grafos
celso.santos@docente.unip.br
24/04/2020
2
Mais avisos...
� Avaliações serão realizadas por listas de exercícios, disponibilizadas
em 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 das
atividades!
Se você não tem impressora...
� As notas das Listas 2 e 3 estarão disponíveis no site na sexta-feira
que vem, dia 01/05.
http://ccsiswift.pro.br/celso.santos
http://ccsiswift.pro.br/celso.santos
2
Mais avisos...
� Avaliações serão realizadas por listas de exercícios, disponibilizadas
em 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 das
atividades!
Se você não tem impressora...
� As notas das Listas 2 e 3 estarão disponíveis no site na sexta-feira
que vem, dia 01/05.
http://ccsiswift.pro.br/celso.santos
http://ccsiswift.pro.br/celso.santos
2
Mais avisos...
� Avaliações serão realizadas por listas de exercícios, disponibilizadas
em 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 das
atividades!
Se você não tem impressora...
� As notas das Listas 2 e 3 estarão disponíveis no site na sexta-feira
que vem, dia 01/05.
http://ccsiswift.pro.br/celso.santos
http://ccsiswift.pro.br/celso.santos
2
Mais avisos...
� Avaliações serão realizadas por listas de exercícios, disponibilizadas
em 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 das
atividades!
Se você não tem impressora...
� As notas das Listas 2 e 3 estarão disponíveis no site na sexta-feira
que vem, dia 01/05.
http://ccsiswift.pro.br/celso.santos
http://ccsiswift.pro.br/celso.santos
2
Mais avisos...
� Avaliações serão realizadas por listas de exercícios, disponibilizadas
em 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 das
atividades!
Se você não tem impressora...
� As notas das Listas 2 e 3 estarão disponíveis no site na sexta-feira
que vem, dia 01/05.
http://ccsiswift.pro.br/celso.santos
http://ccsiswift.pro.br/celso.santos
2
Mais avisos...
� Avaliações serão realizadas por listas de exercícios, disponibilizadas
em 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 das
atividades!
Se você não tem impressora...
� As notas das Listas 2 e 3 estarão disponíveis no site na sexta-feira
que vem, dia 01/05.
http://ccsiswift.pro.br/celso.santos
http://ccsiswift.pro.br/celso.santos
2
Mais avisos...
� Avaliações serão realizadas por listas de exercícios, disponibilizadas
em 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 das
atividades!
Se você não tem impressora...
� As notas das Listas 2 e 3 estarão disponíveis no site na sexta-feira
que vem, dia 01/05.
http://ccsiswift.pro.br/celso.santos
http://ccsiswift.pro.br/celso.santos
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ínimo
Entrada: Um grafo ponderado G = (V,U,w), um vértice fonte s ∈ V e
um 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
Caminho Mínimo
Entrada: Um grafo ponderado G = (V,U,w), um vértice fonte s ∈ V e
um 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
2
3
7
4
5
Caminho Mínimo
Caminho Mínimo
Entrada: Um grafo ponderado G = (V,U,w), um vértice fonte s ∈ V e
um 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
2
3
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
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
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
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
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 todosos vértices
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
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
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
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
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
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
7
Algoritmo de Dijkstra
8
Algoritmo de Dijkstra
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
Algoritmo de Dijkstra
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
Algoritmo de Dijkstra
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);
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
Exemplo de Execução :: Algoritmo de Dijkstra
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
Exemplo de Execução :: Algoritmo de Dijkstra
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
Exemplo de Execução :: Algoritmo de Dijkstra
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
Exemplo de Execução :: Algoritmo de Dijkstra
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
Exemplo de Execução :: Algoritmo de Dijkstra
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
Exemplo de Execução :: Algoritmo de Dijkstra
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
Exemplo de Execução :: Algoritmo de Dijkstra
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
Exemplo de Execução :: Algoritmo de Dijkstra
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
Exemplo de Execução :: Algoritmo de Dijkstra
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
Exemplo de Execução :: Algoritmo de Dijkstra
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
Exemplo de Execução :: Algoritmo de Dijkstra
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
Exemplo de Execução :: Algoritmo de Dijkstra
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
Exemplo de Execução :: Algoritmo de Dijkstra
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
Exemplo de Execução :: Algoritmo de Dijkstra
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
Exemplo de Execução :: Algoritmo de Dijkstra
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
Exemplo de Execução :: Algoritmo de Dijkstra
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
Exemplo de Execução :: Algoritmo de Dijkstra
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
Exemplo de Execução :: Algoritmo de Dijkstra
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
Exemplo de Execução :: Algoritmo de Dijkstra
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
Exemplo de Execução :: Algoritmo de Dijkstra
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
Exemplo de Execução :: Algoritmo de Dijkstra
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
Exemplo de Execução :: Algoritmo de Dijkstra
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
49
Exemplo de Execução :: Algoritmo de Dijkstra
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
Exemplo de Execução :: Algoritmo de Dijkstra
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
Exemplo de Execução :: Algoritmo de Dijkstra
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
Exemplo de Execução :: Algoritmo de Dijkstra
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
Exemplo de Execução :: Algoritmo de Dijkstra
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
Exemplo de Execução :: Algoritmo de Dijkstra
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
Exemplo de Execução :: Algoritmo de Dijkstra
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
2
3
7
4
9
Exemplo de Execução :: Algoritmo de Dijkstra
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
2
3
7
4
9
Exemplo de Execução :: Algoritmo de Dijkstra
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
2
3
7
4
9
Exemplo de Execução :: Algoritmo de Dijkstra
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
2
3
7
4
E QUAL É O SEU CUSTO?
9
Exemplo de Execução :: Algoritmo de Dijkstra
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
2
3
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 pesos
negativos 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
O problema do Dijkstra: Ciclos Negativos
� O algoritmo de Dijkstra funciona mesmo quando existem pesos
negativos 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
O problema do Dijkstra: Ciclos Negativos
� O algoritmo de Dijkstra funciona mesmo quando existem pesos
negativos 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
O problema do Dijkstra: Ciclos Negativos
� O algoritmo de Dijkstra funciona mesmo quando existem pesos
negativos nas arestas.
s
b
c
d
e
f
g
t
-9
3
2 -3
5 5
6
1
5
-23
7
4
� ... mas quebra quando existem ciclos negativos!
11
O problema do Dijkstra: Ciclos Negativos
� O algoritmo de Dijkstra funciona mesmo quando existem pesos
negativos nas arestas.
s
b
c
d
e
f
g
t
-9
3
2 -3
5 5
6
1
5
-23
-7
4
� ... mas quebra quando existem ciclos negativos!
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 False
devolve 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
Exemplo de Execução :: Algoritmo de Bellman-Ford
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
Exemplo de Execução :: Algoritmo de Bellman-Ford
d 0
s
∞
b
∞
c
∞
d
∞
e
π ⊥
s
⊥
b
⊥
c
⊥
d
⊥
e
Ordem das Arestas:
1a : de
2a : bd
3a : sc
4a : bc
5a : sb
6a : cd
7a : ce
s
b
c
d
e
4
3
-2 3
5
6
-1
14
Exemplo de Execução :: Algoritmo de Bellman-Ford
d 0
s
∞
b
∞
c
∞
d
∞
e
π ⊥
s
⊥
b
⊥
c
⊥
d
⊥
e
Ordem das Arestas:
1a : de
2a : bd
3a : sc
4a : bc
5a : sb
6a : cd
7a : ce
s
b
c
d
e
4
3
-2 3
5
6
-1
14
Exemplo de Execução :: Algoritmo de Bellman-Ford
d 0
s
∞
b
∞
c
∞
d
∞
e
π ⊥
s
⊥
b
⊥
c
⊥
d
⊥
e
Ordem das Arestas:
1a : de
2a : bd
3a : sc
4a : bc
5a : sb
6a : cd
7a : ce
s
b
c
d
e
4
3
-2 3
5
6
-1
14
Exemplo de Execução :: Algoritmo de Bellman-Ford
d 0
s
∞
b
∞
c
∞
d
∞
e
π ⊥
s
⊥
b
⊥
c
⊥
d
⊥
e
Ordem das Arestas:
1a : de
2a : bd
3a : sc
4a : bc
5a : sb
6a : cd
7a : ce
s
b
c
d
e
4
3
-2 3
5
6
-1
14
Exemplo de Execução :: Algoritmo de Bellman-Ford
d 0
s
∞
b
3
c
∞
d
∞
e
π ⊥
s
⊥
b
s
c
⊥
d
⊥
e
Ordem das Arestas:
1a : de
2a : bd
3a : sc
4a : bc
5a : sb
6a : cd
7a : ce
s
b
c
d
e
4
3
-2 3
5
6
-1
14
Exemplo de Execução :: Algoritmo de Bellman-Ford
d 0
s
∞
b
3
c
∞
d
∞
e
π ⊥
s
⊥
b
s
c
⊥
d
⊥
e
Ordem das Arestas:
1a : de
2a : bd
3a : sc
4a : bc
5a : sb
6a : cd
7a : ce
s
b
c
d
e
4
3
-2 3
5
6
-1
14
Exemplo de Execução :: Algoritmo de Bellman-Ford
d 0
s
∞
b
3
c
∞
d
∞
e
π ⊥
s
⊥
b
s
c
⊥
d
⊥
e
Ordem das Arestas:
1a : de
2a : bd
3a : sc
4a : bc
5a : sb
6a : cd
7a : ce
s
b
c
d
e
4
3
-2 3
5
6
-1
14
Exemplo de Execução :: Algoritmo de Bellman-Ford
d 0
s
4
b
3
c
∞
d
∞
e
π ⊥
s
s
b
s
c
⊥
d
⊥
e
Ordem das Arestas:
1a : de
2a : bd
3a : sc
4a : bc
5a : sb
6a : cd
7a : ce
s
b
c
d
e
4
3
-2 3
5
6
-1
14
Exemplo de Execução :: Algoritmo de Bellman-Ford
d 0
s
4
b
3
c
∞
d
∞
e
π ⊥
s
s
b
s
c
⊥
d
⊥
e
Ordem das Arestas:
1a : de
2a : bd
3a : sc
4a : bc
5a : sb
6a : cd
7a : ce
s
b
c
d
e
4
3
-2 3
5
6
-1
14
Exemplo de Execução :: Algoritmo de Bellman-Ford
d 0
s
4
b
3
c
6
d
∞
e
π ⊥
s
s
b
s
c
c
d
⊥
e
Ordem das Arestas:
1a : de
2a : bd
3a : sc
4a : bc
5a : sb
6a : cd
7a : ce
s
b
c
d
e
4
3
-2 3
5
6
-1
14
Exemplo de Execução :: Algoritmo de Bellman-Ford
d 0
s
4
b
3
c
6
d
∞
e
π ⊥
s
s
b
s
c
c
d
⊥
e
Ordem das Arestas:
1a : de
2a : bd
3a : sc
4a : bc
5a : sb
6a : cd
7a : ce
s
b
c
d
e
4
3
-2 3
5
6
-1
14
Exemplo de Execução :: Algoritmo de Bellman-Ford
d 0
s
4
b
3
c
6
d
9
e
π ⊥
s
s
b
s
c
c
d
c
e
Ordem das Arestas:
1a : de
2a : bd
3a : sc
4a : bc
5a : sb
6a : cd
7a : ce
s
b
c
d
e
4
3
-2 3
5
6
-1
14
Exemplo de Execução :: Algoritmo de Bellman-Ford
d 0
s
4
b
3
c
6
d
9
e
π ⊥
s
s
b
s
c
c
d
c
e
Ordem das Arestas:
1a : de
2a : bd
3a : sc
4a : bc
5a : sb
6a : cd
7a : ce
s
b
c
d
e
4
3
-2 3
5
6
-1
ACABOU O ALGORITMO?
14
Exemplo de Execução :: Algoritmo de Bellman-Ford
d 0
s
4
b
3
c
6
d
9
e
π ⊥
s
s
b
s
c
c
d
c
e
Ordem das Arestas:
1a : de
2a : bd
3a : sc
4a : bc
5a : sb
6a : cd
7a : ce
s
b
c
d
e
4
3
-2 3
5
6
-1
14
Exemplo de Execução :: Algoritmo de Bellman-Ford
d 0
s
4
b
3
c
6
d
5
e
π ⊥
s
s
b
s
c
c
d
d
e
Ordem das Arestas:
1a : de
2a : bd
3a : sc
4a : bc
5a : sb
6a : cd
7a : ce
s
b
c
d
e
4
3
-2 3
5
6
-1
14
Exemplo de Execução :: Algoritmo de Bellman-Ford
d 0
s
4
b
3
c
6
d
5
e
π ⊥
s
s
b
s
c
c
d
d
e
Ordem das Arestas:
1a : de
2a : bd
3a : sc
4a : bc
5a : sb6a : cd
7a : ce
s
b
c
d
e
4
3
-2 3
5
6
-1
14
Exemplo de Execução :: Algoritmo de Bellman-Ford
d 0
s
4
b
3
c
6
d
5
e
π ⊥
s
s
b
s
c
c
d
d
e
Ordem das Arestas:
1a : de
2a : bd
3a : sc
4a : bc
5a : sb
6a : cd
7a : ce
s
b
c
d
e
4
3
-2 3
5
6
-1
14
Exemplo de Execução :: Algoritmo de Bellman-Ford
d 0
s
4
b
3
c
6
d
5
e
π ⊥
s
s
b
s
c
c
d
d
e
Ordem das Arestas:
1a : de
2a : bd
3a : sc
4a : bc
5a : sb
6a : cd
7a : ce
s
b
c
d
e
4
3
-2 3
5
6
-1
14
Exemplo de Execução :: Algoritmo de Bellman-Ford
d 0
s
4
b
2
c
6
d
5
e
π ⊥
s
s
b
b
c
c
d
d
e
Ordem das Arestas:
1a : de
2a : bd
3a : sc
4a : bc
5a : sb
6a : cd
7a : ce
s
b
c
d
e
4
3
-2 3
5
6
-1
14
Exemplo de Execução :: Algoritmo de Bellman-Ford
d 0
s
4
b
2
c
6
d
5
e
π ⊥
s
s
b
b
c
c
d
d
e
Ordem das Arestas:
1a : de
2a : bd
3a : sc
4a : bc
5a : sb
6a : cd
7a : ce
s
b
c
d
e
4
3
-2 3
5
6
-1
14
Exemplo de Execução :: Algoritmo de Bellman-Ford
d 0
s
4
b
2
c
6
d
5
e
π ⊥
s
s
b
b
c
c
d
d
e
Ordem das Arestas:
1a : de
2a : bd
3a : sc
4a : bc
5a : sb
6a : cd
7a : ce
s
b
c
d
e
4
3
-2 3
5
6
-1
14
Exemplo de Execução :: Algoritmo de Bellman-Ford
d 0
s
4
b
2
c
5
d
5
e
π ⊥
s
s
b
b
c
c
d
d
e
Ordem das Arestas:
1a : de
2a : bd
3a : sc
4a : bc
5a : sb
6a : cd
7a : ce
s
b
c
d
e
4
3
-2 3
5
6
-1
14
Exemplo de Execução :: Algoritmo de Bellman-Ford
d 0
s
4
b
2
c
5
d
5
e
π ⊥
s
s
b
b
c
c
d
d
e
Ordem das Arestas:
1a : de
2a : bd
3a : sc
4a : bc
5a : sb
6a : cd
7a : ce
s
b
c
d
e
4
3
-2 3
5
6
-1
14
Exemplo de Execução :: Algoritmo de Bellman-Ford
d 0
s
4
b
2
c
5
d
5
e
π ⊥
s
s
b
b
c
c
d
d
e
Ordem das Arestas:
1a : de
2a : bd
3a : sc
4a : bc
5a : sb
6a : cd
7a : ce
s
b
c
d
e
4
3
-2 3
5
6
-1
ACABOU O ALGORITMO?
14
Exemplo de Execução :: Algoritmo de Bellman-Ford
d 0
s
4
b
2
c
5
d
5
e
π ⊥
s
s
b
b
c
c
d
d
e
Ordem das Arestas:
1a : de
2a : bd
3a : sc
4a : bc
5a : sb
6a : cd
7a : ce
s
b
c
d
e
4
3
-2 3
5
6
-1
14
Exemplo de Execução :: Algoritmo de Bellman-Ford
d 0
s
4
b
2
c
5
d
5
e
π ⊥
s
s
b
b
c
c
d
d
e
Ordem das Arestas:
1a : de
2a : bd
3a : sc
4a : bc
5a : sb
6a : cd
7a : ce
s
b
c
d
e
4
3
-2 3
5
6
-1
14
Exemplo de Execução :: Algoritmo de Bellman-Ford
d 0
s
4
b
2
c
5
d
5
e
π ⊥
s
s
b
b
c
c
d
d
e
Ordem das Arestas:
1a : de
2a : bd
3a : sc
4a : bc
5a : sb
6a : cd
7a : ce
s
b
c
d
e
4
3
-2 3
5
6
-1
ACABOU O ALGORITMO?
14
Exemplo de Execução :: Algoritmo de Bellman-Ford
d 0
s
4
b
2
c
5
d
5
e
π ⊥
s
s
b
b
c
c
d
d
e
Ordem das Arestas:
1a : de
2a : bd
3a : sc
4a : bc
5a : sb
6a : cd
7a : ce
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 : bc
2a : ca
3a : ab
a
b
c
4
3
-8
15
Exemplo de Execução (Ruim) :: Algoritmo de Bellman-Ford
d 0
a
4
b
∞
c
π ⊥
a
s
b
⊥
c
Ordem das Arestas:
1a : bc
2a : ca
3a : ab
a
b
c
4
3
-8
15
Exemplo de Execução (Ruim) :: Algoritmo de Bellman-Ford
d −1
a
4
b
−4
c
π c
a
s
b
b
c
Ordem das Arestas:
1a : bc
2a : ca
3a : ab
a
b
c
4
3
-8
15
Exemplo de Execução (Ruim) :: Algoritmo de Bellman-Ford
d −1
a
4
b
−4
c
π c
a
s
b
b
c
Ordem das Arestas:
1a : bc
2a : ca
3a : ab
a
b
c
4
3
-8
ACABOU O ALGORITMO?
15
Exemplo de Execução (Ruim) :: Algoritmo de Bellman-Ford
d −1
a
4
b
−4
c
π c
a
s
b
b
c
Ordem das Arestas:
1a : bc
2a : ca
3a : ab
a
b
c
4
3
-8
15
Exemplo de Execução (Ruim) :: Algoritmo de Bellman-Ford
d −1
a
4
b
−4
c
π c
a
s
b
b
c
Ordem das Arestas:
1a : bc
2a : ca
3a : ab
a
b
c
4
3
-8
15
Exemplo de Execução (Ruim) :: Algoritmo de Bellman-Ford
d −1
a
4
b
−4
c
π c
a
s
b
b
c
Ordem das Arestas:
1a : bc
2a : ca
3a : ab
a
b
c
4
3
-8
15
Exemplo de Execução (Ruim) :: Algoritmo de Bellman-Ford
d −1
a
4
b
−4
c
π c
a
s
b
b
c
Ordem das Arestas:
1a : bc
2a : ca
3a : ab
a
b
c
4
3
-8
15
Exemplo de Execução (Ruim) :: Algoritmo de Bellman-Ford
d −1
a
4
b
−4
c
π c
a
s
b
b
c
Ordem das Arestas:
1a : bc
2a : ca
3a : ab
a
b
c
4
3
-8
d[b] > d[a] + w(a, b)!
15
Exemplo de Execução (Ruim) :: Algoritmo de Bellman-Ford
d −1
a
4
b
−4
c
π c
a
s
b
b
c
Ordem das Arestas:
1a : bc
2a : ca
3a : ab
a
b
c
4
3
-8
Algoritmo devolve False!!
16
Comparando os Algoritmos
Algoritmos para resolver Caminho Mínimo
� 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
Comparando os Algoritmos
Algoritmos para resolver Caminho Mínimo
� 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
Comparando os Algoritmos
Algoritmos para resolver Caminho Mínimo
� 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
Comparando os Algoritmos
Algoritmos para resolver Caminho Mínimo
� 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
Comparando os Algoritmos
Algoritmos para resolver Caminho Mínimo
� 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
Comparando os Algoritmos
Algoritmos para resolver Caminho Mínimo
� 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
Comparando os Algoritmos
Algoritmos para resolver Caminho Mínimo
� 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
Comparando os Algoritmos
Algoritmos para resolver Caminho Mínimo
� 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
Comparando os Algoritmos
Algoritmos para resolver Caminho Mínimo
� 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
Comparando os Algoritmos
Algoritmos para resolver Caminho Mínimo
� 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)
17
Dúvidas?
18
Aula que vem...
19
Árvore Geradora Mínima
v1
v2
v3
v4 v5
v6
v7
v8
30
18
25
23
15
28
17
33
21
22
3227
31 35
19
Árvore Geradora Mínima
Entrada: 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
v7
v8
30
18
25
23
15
28
17
33
21
22
3227
31 35
19
Árvore Geradora Mínima
Entrada: Um grafo ponderado G = (V,U,w).
Pergunta: Qual é a árvore T ⊆ G de custo mínimo que gera G?
	Na aula passada...
	Algoritmo de Dijkstra
	O Algoritmo de Bellman-Ford
	Dúvidas?
	Aula que vem...