Caminho P.O II

Prévia do material em texto

Grafos
Raphael Ramos
Problema do menor caminho
Como encontrar o menor caminho em um grafo?
Problema do menor caminho
Imagine que uma transportadora decidiu alavancar as suas
entregas e fez uma promoc¸a˜o de 50% em todas as entregas da
cidade A ate´ a cidade F. Para que ela na˜o tenha preju´ızo ela
tera´ sempre que percorrer o menor caminho entre as cidades.
Como fazer isso?
A
B
D
C
E
F
Problema do menor caminho
Problema
Obter Caminhos interligando ve´rtices de um grafo, cujo
comprimento (custo) seja m´ınimo.
Implementac¸o˜es
Algoritmo de Dijkstra, Algoritmo de Bellman-Ford
Problema do menor caminho
Aplicac¸a˜o
• Redes de Computadores (Percurso entre Roteadores);
• Tra´fego Urbano;
• Sistemas Rodovia´rios, Ferrovia´rios e Ae´reos;
• Importante para va´rios outros problemas
Algoritmo de Dijikstra
Problema dos caminhos mais curtos de origem u´nica: para um
dado ve´rtice, chamado fonte, em um grafo ponderado
conectado, encontrar os caminhos mais curtos a todos os
outros ve´rtices.
Algoritmo de Dijikstra
Melhor algoritmo conhecido aplicado a grafos com pesos na˜o
negativos.
Algoritmo de Dijikstra
• Encontra os caminhos mais curtos de acordo com a
distaˆncia a uma dada fonte.
• Primeiro,encontra o caminho mais curto da fonte ao
ve´rtice mais pro´ximo e assim por diante.
• Em geral, antes da i-e´sima iterac¸a˜o iniciar, o algoritmo ja´
encontrou os menores caminhos para os outros i-1
ve´rtices pro´ximos da fonte.
Algoritmo de Dijikstra
• Estes ve´rtices, a fonte, e as arestas dos caminhos mais
curtos formam uma sub-a´rvore Ti.
• Como todos os pesos das arestas sa˜o na˜o negativos, o
ve´rtice seguinte mais pro´ximo da fonte pode ser
encontrado dentre os ve´rtices adjacentes aos ve´rtices de
Ti.
• Para identificar o i-e´simo ve´rtice mais pro´ximo, o
algoritmo calcula, para cada ve´rtice candidato u, a soma
da distaˆncia ao ve´rtice da a´rvore v mais pro´ximo e o
comprimento dv do caminho mais curto da fonte a` v e
enta˜o seleciona o ve´rtice cuja soma seja a menor.
Algoritmo de Dijikstra
Cada ve´rtice possui duas etiquetas:
• Um valor nume´rico d que indica o comprimento do
caminho mais curto da fonte ao ve´rtice encontrado pelo
algoritmo ate´ o momento. Quando um ve´rtice for
adicionado a a´rvore, d indica o comprimento do caminho
mais curto da fonte ate´ o ve´rtice.
• A outra etiqueta indica o nome do pro´ximo ao u´ltimo
ve´rtice neste caminho, i.e., o pai do ve´rtice na a´rvore
sendo constru´ıda.
Algoritmo de Dijikstra
• Com estas etiquetas, encontrar o ve´rtice mais pro´ximo u*
seguinte torna-se uma tarefa simples que consiste em
encontrar o ve´rtice candidato com o menor valor de d.
Algoritmo de Dijikstra
Apo´s identificado o ve´rtice u* a ser adicionado a a´rvore, as
seguintes operac¸o˜es devem ser realizadas:
• Mover o ve´rtice u* do ve´rtice candidato para o conjunto
dos ve´rtices da a´rvore;
• Para cada ve´rtice candidato remanescente u que estiver
conectado a u* por uma aresta de pesos(u*,u) tal que
du* + w(u*,u) ¡ dw, atualize as etiquetas de u por u* e
du* + w(u*,u) respectivamente.
Algoritmo de Dijikstra
Topologia da rede, custos dos enlaces conhecidos por todos os
no´s
• Realizado atrave´s de “difusa˜o do estado dos enlaces”;
• Todos os no´s teˆm mesma info.
Algoritmo de Dijikstra
Calcula caminhos de menor custo de um no´ origem para todos
os demais
• gera tabela de rotas para aquele no´
Algoritmo de Dijikstra
Iterativo: depois de k iterac¸o˜es, sabemos menor custo para k
destinos
Notac¸a˜o
• c(i,j): custo do enlace do no´ i ao no´ j. custo e´ infinito se
na˜o forem vizinhos diretos;
• D(V): valor corrente do custo do caminho da origem ao
destino V;
• p(V): no´ antecessor no caminho da origem ao no´ V;
• N conjunto de no´s cujo caminho de menor custo ja´ foi
determinado
O algoritmo de Dijkstra
1- Inicializac¸a˜o:
2- N = A
3- para todos os no´s V
4- se V for adjacente ao no´ A
5- enta˜o D(V) = c(A,V)
6- sena˜o D(V) = infinito
7- Repete
8- determina W na˜o contido em N tal que D(W) e´ o m´ınimo
9- adiciona W ao conjunto N
10- atualiza D(V) para todo V adjacente ao no´ W e ainda na˜o
em N:
11- D(V) = min( D(V), D(W) + c(W,V) )
12- /* novo custo ao no´ V ou e´ o custo velho a V ou o custo
do
13- menor caminho ao no´ W, mais o custo de W a V */
14- ate´ que todos no´s estejam em N
Exemplo
A
B
D
C
E
F
2
3
5
2
3
3
1
1
1
5
2
Resoluc¸a˜o do exemplo
Tabela: 1
Ve´rtices A B C D E F Ω
Estimativas 0 ∞ ∞ ∞ ∞ ∞ {A}
Precedentes - - - - - -
Resoluc¸a˜o do exemplo
Tabela: 2
Ve´rtices A B C D E F Ω
Estimativas 2 5 3 ∞ ∞ {B}
Precedentes A A A - -
Resoluc¸a˜o do exemplo
Tabela: 3
Ve´rtices A B C D E F Ω
Estimativas 5 3 ∞ ∞ {D}
Precedentes A A - -
Resoluc¸a˜o do exemplo
Tabela: 4
Ve´rtices A B C D E F Ω
Estimativas 5 4 ∞ {E}
Precedentes A D -
Resoluc¸a˜o do exemplo
Tabela: 5
Ve´rtices A B C D E F Ω
Estimativas 5 6 {C}
Precedentes A E
Resoluc¸a˜o do exemplo
Tabela: 6
Ve´rtices A B C D E F Ω
Estimativas 6 {F}
Precedentes A E
Soluc¸a˜o
Ω = {A,B,D,E,F,C}
Se queremos encontrar o caminho m´ınimo entre os no´s A e F,
e´ so´ trac¸armos o caminho dos precedentes dos no´s, por
exemplo:
F seu precedente e´ E.
E seu precedente e´ D.
D seu precedente e´ A.
Enta˜o o caminho m´ınimo entre A e F e´ {A-D-E-F}
Exemplo 2
A
B
C
D
E
F
2
3
5
2
5
1
2
4
Resoluc¸a˜o do exemplo
Tabela: 1
Ve´rtices A B C D E F Ω
Estimativas 0 ∞ ∞ ∞ ∞ ∞ {A}
Precedentes - - - - - -
Resoluc¸a˜o do exemplo
Tabela: 2
Ve´rtices A B C D E F Ω
Estimativas 2 3 ∞ ∞ ∞ {B}
Precedentes A A - - -
Resoluc¸a˜o do exemplo
Tabela: 3
Ve´rtices A B C D E F Ω
Estimativas 3 7 4 ∞ {C}
Precedentes A B B -
Resoluc¸a˜o do exemplo
Tabela: 4
Ve´rtices A B C D E F Ω
Estimativas 7 4 {E}
Precedentes B B
Resoluc¸a˜o do exemplo
Tabela: 5
Ve´rtices A B C D E F Ω
Estimativas 5 8 {D}
Precedentes E E
Resoluc¸a˜o do exemplo
Tabela: 6
Ve´rtices A B C D E F Ω
Estimativas 7 {F}
Precedentes D
Soluc¸a˜o
Ω = {A,B,D,E,F,C}
Se queremos encontrar o caminho m´ınimo entre os no´s A e F,
e´ so´ trac¸armos o caminho dos precedentes dos no´s, por
exemplo:
F seu precedente e´ D.
D seu precedente e´ E.
E seu precedente e´ B.
B seu precedente e´ A.
Enta˜o o caminho m´ınimo entre A e F e´ {A-B-E-D-F}
Exemplo 3
A
D
B
G
E
C
F Z
5
4
2
1
2
1
5
1
3
1
1
2
Resoluc¸a˜o do exemplo
Tabela: 1
Ve´rtices A B C D E F G Z Ω
Estimativas 0 ∞ ∞ ∞ ∞ ∞ ∞ ∞ {A}
Precedentes - - - - - - - -
Resoluc¸a˜o do exemplo
Tabela: 1
Ve´rtices A B C D E F G Z Ω
Estimativas 4 ∞ 5 ∞ ∞ 2 ∞ {G}
Precedentes A - A - - A -
Resoluc¸a˜o do exemplo
Tabela: 2
Ve´rtices A B C D E F G Z Ω
Estimativas 3 ∞ 3 ∞ ∞ ∞ {B}
Precedentes G - G - - -
Resoluc¸a˜o do exemplo
Tabela: 3
Ve´rtices A B C D E F G Z Ω
Estimativas 8 3 ∞ ∞ ∞ {D}
Precedentes B G - - -
Resoluc¸a˜o do exemplo
Tabela: 4
Ve´rtices A B C D E F G Z Ω
Estimativas 8 5 ∞ ∞ {E}
Precedentes B D - -
Resoluc¸a˜o do exemplo
Tabela: 5
Ve´rtices A B C D E F G Z Ω
Estimativas 8 6 8 {F}
Precedentes B E E
Resoluc¸a˜o do exemplo
Tabela: 6
Ve´rtices A B C D E F G Z Ω
Estimativas 8 8 {C}
Precedentes B E
Resoluc¸a˜o do exemplo
Tabela: 7
Ve´rtices A B C D E F G Z Ω
Estimativas 8 {Z}
Precedentes E
Soluc¸a˜o
Ω = {A,G,B,D,E,F,C,Z}
Se queremos encontrar o caminho m´ınimo entre os no´s A e Z,
e´ so´ trac¸armos o caminho dos precedentes dos no´s, por
exemplo:
Z seu precedente e´ E.
E seu precedente e´ D.
D seu precedente e´ G.
G seu precedentee´ A.
Enta˜o o caminho m´ınimo entre A e F e´ {A-G-D-E-Z}
Exemplo 4
S
U
X
V
Y
10
5
1
3 2
9
2
6 4
7
Resoluc¸a˜o do exemplo
Tabela: 1
Ve´rtices S U X V Y Ω
Estimativas 0 ∞ ∞ ∞ ∞ {A}
Precedentes - - - - -
Resoluc¸a˜o do exemplo
Tabela: 2
Ve´rtices S U X V Y Ω
Estimativas 10 5 ∞ ∞ {X}
Precedentes - S S - -
Resoluc¸a˜o do exemplo
Tabela: 3
Ve´rtices S U X V Y Ω
Estimativas 7 14 7 {U}
Precedentes - X - X X
Resoluc¸a˜o do exemplo
Tabela: 4
Ve´rtices S U X V Y Ω
Estimativas 8 7 {Y}
Precedentes - - - U X
Resoluc¸a˜o do exemplo
Tabela: 5
Ve´rtices S U X V Y Ω
Estimativas 8 {V}
Precedentes - - - U -
Soluc¸a˜o
Ω = {S,X,U,Y,V}
Se queremos encontrar o caminho m´ınimo entre os no´s S e V,
e´ so´ trac¸armos o caminho dos precedentes dos no´s, por
exemplo:
V seu precedente e´ U.
U seu precedente e´ X.
X seu precedente e´ S.
Enta˜o o caminho m´ınimo entre A e F e´ {S-X-U-V}
Exemplo 5
Encontre o caminho m´ınimo de A a G
A
B
C
D
E
F
G
3
7
9
5
9
2
9
3
8
10
3
3
Resoluc¸a˜o do exemplo 5
Tabela: 1
Ve´rtices A B C D E F G Ω
Estimativas 0 ∞ ∞ ∞ ∞ ∞ ∞ {A}
Precedentes - - - - - - -
Resoluc¸a˜o do exemplo 5
Tabela: 2
Ve´rtices A B C D E F G Ω
Estimativas 3 7 9 ∞ ∞ ∞ {B}
Precedentes A A A - - -
Resoluc¸a˜o do exemplo 5
Tabela: 3
Ve´rtices A B C D E F G Ω
Estimativas 7 8 12 ∞ ∞ {C}
Precedentes A B B - -
Resoluc¸a˜o do exemplo 5
Tabela: 4
Ve´rtices A B C D E F G Ω
Estimativas 8 12 16 ∞ {D}
Precedentes - B B C -
Resoluc¸a˜o do exemplo 5
Tabela: 5
Ve´rtices A B C D E F G Ω
Estimativas 11 16 18 {E}
Precedentes - D C D
Resoluc¸a˜o do exemplo 5
Tabela: 6
Ve´rtices A B C D E F G Ω
Estimativas 16 14 {G}
Precedentes - C E
Resoluc¸a˜o do exemplo 5
Tabela: 7
Ve´rtices A B C D E F G Ω
Estimativas 16 {F}
Precedentes - C
Caminho m´ınimo - A - B - D - E - G Valor = 14
Exemplo 6
Encontre o caminho m´ınimo de A a F
A B C
D E F
1
4
5
7
3
6
9
8 2
Resoluc¸a˜o do exemplo 6
Tabela: 1
Ve´rtices A B C D E F Ω
Estimativas 0 ∞ ∞ ∞ ∞ ∞ {A}
Precedentes - - - - - -
Resoluc¸a˜o do exemplo 6
Tabela: 2
Ve´rtices A B C D E F Ω
Estimativas 1 ∞ 4 ∞ ∞ {B}
Precedentes A - A - -
Resoluc¸a˜o do exemplo 6
Tabela: 3
Ve´rtices A B C D E F Ω
Estimativas 6 4 4 7 {D}
Precedentes B A B B
Resoluc¸a˜o do exemplo 6
Tabela: 4
Ve´rtices A B C D E F Ω
Estimativas 6 4 7 {E}
Precedentes B B B
Resoluc¸a˜o do exemplo 6
Tabela: 5
Ve´rtices A B C D E F Ω
Estimativas 6 6 {C}
Precedentes B E
Resoluc¸a˜o do exemplo 6
Tabela: 5
Ve´rtices A B C D E F Ω
Estimativas 6 {F}
Precedentes E
Caminho m´ınimo - A - B - E - F Valor = 6
Exemplo 7
Encontre o caminho m´ınimo de A a M.
A B C D
E F G H
I J L M
4
7
3
8
6
6 8
8
2
6
3
8
1 8
3 1 8
Resoluc¸a˜o do exemplo 7
Ve´rtices A B C D E F G H I J L M Ω
Estimativas 0 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ {A}
Precedentes - - - - - - - - - - - -
Tabela: 1
Resoluc¸a˜o do exemplo 7
Ve´rtices A B C D E F G H I J L M Ω
Estimativas 4 ∞ ∞ 7 ∞ ∞ ∞ ∞ ∞ ∞ ∞ {B}
Precedentes A - - A - - - - - - -
Tabela: 2
Resoluc¸a˜o do exemplo 7
Ve´rtices A B C D E F G H I J L M Ω
Estimativas 7 ∞ 7 12 ∞ ∞ ∞ ∞ ∞ ∞ {C}
Precedentes B - A B - - - - - -
Tabela: 3
Resoluc¸a˜o do exemplo 7
Ve´rtices A B C D E F G H I J L M Ω
Estimativas 13 7 12 13 ∞ ∞ ∞ ∞ ∞ {E}
Precedentes C A B C - - - - -
Tabela: 4
Resoluc¸a˜o do exemplo 7
Ve´rtices A B C D E F G H I J L M Ω
Estimativas 13 12 13 ∞ 9 ∞ ∞ ∞ {I}
Precedentes C B C - E - - -
Tabela: 5
Resoluc¸a˜o do exemplo 7
Ve´rtices A B C D E F G H I J L M Ω
Estimativas 13 12 13 ∞ 12 ∞ ∞ {F}
Precedentes C B C - I - -
Tabela: 6
Resoluc¸a˜o do exemplo 7
Ve´rtices A B C D E F G H I J L M Ω
Estimativas 13 13 ∞ 12 ∞ ∞ {J}
Precedentes C C - I - -
Tabela: 7
Resoluc¸a˜o do exemplo 7
Ve´rtices A B C D E F G H I J L M Ω
Estimativas 13 13 ∞ 13 ∞ {D}
Precedentes C C - J -
Tabela: 8
Resoluc¸a˜o do exemplo 7
Ve´rtices A B C D E F G H I J L M Ω
Estimativas 13 21 13 ∞ {G}
Precedentes C D J -
Tabela: 9
Resoluc¸a˜o do exemplo 7
Ve´rtices A B C D E F G H I J L M Ω
Estimativas 21 13 ∞ {L}
Precedentes D J -
Tabela: 10
Resoluc¸a˜o do exemplo 7
Ve´rtices A B C D E F G H I J L M Ω
Estimativas 21 21 {H}
Precedentes D L
Tabela: 11
Resoluc¸a˜o do exemplo 7
Ve´rtices A B C D E F G H I J L M Ω
Estimativas 21 {M}
Precedentes L
Tabela: 12
Caminho m´ınimo - A - E - I - J - L - M
Valor = 21