CR Modulo4

BC0506 - Comunicação e Redes
Algoritmos de caminhos mínimos
Prof. Vladi
Baseados nos slides dos professores de CR
Jesús, Fabrício, Carlos K.
Algoritmos de caminhos mínimos
Caminhos mínimos - Motivação
Existem diversos caminhos que podem ser percorridos para

chegar de um vértice a outro (e.g, enviar uma informação).
Qual seria (e como encontrar) o melhor caminho?
A busca em largura não fornece isso?

Reparem que em um grafo ponderado (com valores nas

arestas) o melhor caminho não necessariamente é o que
percorre menos arestas. Veja por exemplo de A a F.
Caminho com menos arestas:

2 1
B C (busca em largura)
A A, G, E, F
1
5 Custo = 5+3+1 = 9
3 E 2
G 1 D Caminho com menor custo:
2 (???)
H A, B, C, D, E, F
F
Custo = 2+1+1+2+1 = 7
Motivação
Existem diversos caminhos que podem ser percorridos para
chegar de um vértice a outro (e.g, enviar uma informação).
Ideia:
Minimizar (ou maximizar) um determinado valor.
Por exemplo:
- Minimizar o custo ou o tempo gasto.
- Maximizar o lucro ou o ganho.
Exemplo 1
Considere uma empresa de entregas, com um centro de
distribuição e um caminhão.
Problema:
Dada uma lista de endereços de entrega encontrar uma
sequência que minimize a kilometragem total do caminhão
para realizar todas as entregas
Modelar o problema através de grafos.
Vértices:
Endereços de entrega.
Arestas:
Uma rota conectando 2
endereços de entrega.
Peso/custo:
Distâncias entre as
extremidades.
Exemplo 2
Considere um programa de GPS para o cálculo da “melhor
rota” entre dois pontos.
Problema:
Dado um endereço de origem e destino, encontrar um
camino mínimo entre a origem e o destino, i.e., encontrar a
rota com a menor distância.
Modelar o problema através de grafos.
Vértices:
Cruzamentos entre ruas.
Arestas:
Cada trecho de rua.
Peso/custo:
Comprimento do trecho (em
kilometros)
Distância
No grafo, um caminho C é mínimo se não existe outro

caminho (com mesmo origem-destino que C) com um
comprimento menor.
Lembrando que a distância entre s e t é o comprimento do

caminho mínimo entre s e t.
Se não existe caminho algúm entre s e t, então a distância

entre ambos vértices é infinita.
Distância
Grafos não-ponderados (distância usa a qtde. de arestas)
b c Distância entre:
h,e = 3
h,k = Infinito
a d f
e k
Distância
Grafos ponderados (distância usa a ponderação das arestas)
Muitas aplicações associam

h
um número a cada aresta.
1
1
b c Esse número é o
custo/peso da aresta, que
5 7 1
pode ser associado a uma
característica física da
a d f
2 10 conexão.
3 7
E.g., distância para
e k percorrer estradas; energia
elêtrica utilizada; tempo
para receber informações
da Internet
Distância
h
1
1
h,k = Infinito
5 7 1
h,e = ?
a d f
2 10
3 7
e k
Distância
h
1
1
h,k = Infinito
5 7 1
h,e = 8
a d f
2 10
3 7
e k
Distância
h
1
1
h,k = Infinito
5 7 1
h,e = 8
a d f
2 10 O comprimento de
um caminho é a
3 7
soma dos
e k pesos/custos das
arestas do caminho.
Busca de caminhos mínimos em grafos
Para a busca de caminhos mínimos em grafos

ponderados, existem algoritmos específicos que executam a
tarefa.
Algoritmos específicos:
(1) Caminhos mínimos a partir de um determinado vértice.
(2) Caminos mínimos entre todos os pares de vértices.
Dijkstra: mínimos a partir de um vértice
Caminho mínimos com origem fixa
Dado um vértice s de um grafo ponderado, encontrar para

cada vértice t (que pode ser alcançado a partir de s) um
caminho mínimo de s a t.
Todos os algoritmos para esses problemas exploram a

seguinte propriedade triangular:
d(x,z) ≤ d(x,y)+d(y,z)
sendo d(i,j) a distância do vértice i ao vértice j.

Algoritmo de Dijkstra
Algoritmo eficiente para a obtenção do caminho mínimo em

grafos com pesos (ponderações) não-negativos.
Criado pelo cientista da computação Edsger Dijkstra em 1956
Entrada:
Grafo, G.
Vértices, s.
Pesos, w (não-negativos).
Saída:
Caminhos mínimos a partir de s.
Começando no vértice a
a
1 10
3
b e
5 1 6
c d
2
iteração Vértices a.dis b.dis c.dis d.dis e.dis

∞ visitados
a 0 {} ∞ ∞ ∞ ∞ ∞
1 10
∞ 3 ∞
b e
5 1 6
c d
∞ 2 ∞

0 visitados
a 0 {} ∞ ∞ ∞ ∞ ∞
1 10 1 {a} 0 1 ∞ 3 10
1 3 10
b e
5 1 6
c d
∞ 2 3

0 visitados
a 0 {} ∞ ∞ ∞ ∞ ∞
1 10 1 {a} 0 1 ∞ 3 10
1 3 10 2 {a,b} 0 1 6 3 10
b e
5 1 6
c d
6 2 3

0 visitados
a 0 {} ∞ ∞ ∞ ∞ ∞
1 10 1 {a} 0 1 ∞ 3 10
1 3 9 2 {a,b} 0 1 6 3 10
b e
3 {a,b,d} 0 1 5 3 9
5 1 6
c d
5 2 3

0 visitados
a 0 {} ∞ ∞ ∞ ∞ ∞
1 10 1 {a} 0 1 ∞ 3 10
1 3 6 2 {a,b} 0 1 6 3 10
b e
3 {a,b,d} 0 1 5 3 9
4 {a,b,d,c} 0 1 5 3 6
5 1 6
c d
5 2 3

0 visitados
a 0 {} ∞ ∞ ∞ ∞ ∞
1 10 1 {a} 0 1 ∞ 3 10
1 3 6 2 {a,b} 0 1 6 3 10
b e
3 {a,b,d} 0 1 5 3 9
4 {a,b,d,c} 0 1 5 3 6
5 1 6 5 {a,b,d,c,e} 0 1 5 3 6
c d
5 2 3
Inicialização:
Atribui uma distância infinita para todos os vértices.
O vértice de origem recebe distância zero (0).
Todos os vértices são marcados como não visitados.
Enquanto houveram vértices não visitados:

Escolha o vértice não visitado com a menor distância (a partir
da origem) como o vértice atual.
Calcule a distância para todos os vértices adjacêntes não
visitados:
- Se a distância é menor, substitua a distância.
- Marque-o como visitado (sua distância é mínima).
Começando no vértice b
a
2 4
3
b e
6
7
3 3
c d
2
∞
visitados
a 0 {} ∞ ∞ ∞ ∞ ∞
2 4
∞
b
6
3
e ∞
7
3 3
c d
∞ 2 ∞

2 visitados
a 0 {} ∞ ∞ ∞ ∞ ∞
2 4 1 {b} 2 0 3 6 ∞
0
b
6
3
e ∞
7
3 3
c d
3 2 6

2 visitados
a 0 {} ∞ ∞ ∞ ∞ ∞
2 4 1 {b} 2 0 3 6 ∞
0 3 2 {b,a} 2 0 3 6 6
b e 6
6
7
3 3
c d
3 2 6

2 visitados
a 0 {} ∞ ∞ ∞ ∞ ∞
2 4 1 {b} 2 0 3 6 ∞
0 3 2 {b,a} 2 0 3 6 6
b e 6
6 3 {b,a,c} 2 0 3 5 6
7
3 3
c d
3 2 5

2 visitados
a 0 {} ∞ ∞ ∞ ∞ ∞
2 4 1 {b} 2 0 3 6 ∞
0 3 2 {b,a} 2 0 3 6 6
b e 6
6 3 {b,a,c} 2 0 3 5 6
7
4 {b,a,c,d} 2 0 3 5 6
3 3
c d
3 2 5

2 visitados
a 0 {} ∞ ∞ ∞ ∞ ∞
2 4 1 {b} 2 0 3 6 ∞
0 3 2 {b,a} 2 0 3 6 6
b e 6
6 3 {b,a,c} 2 0 3 5 6
7
4 {b,a,c,d} 2 0 3 5 6
3 3 5 {b,a,c,d,e} 2 0 3 5 6
c d
3 2 5
Dijkstra(G,s,w)
Para cada vértice v em G Inicialização
v.dis = INFINITO
v.pre = VAZIO
s.dis = 0
T = todos os vértices de G
Percorre o grafo
Enquanto T != VAZIO faça
u = vértice em T com menor distância
remove u de T
Para cada vizinho v de u
d = u.dist + w(u,v)
Se d < v.dist
v.dist = d
v.pre = u
1
t x
10 9
2 3
s
4 6
5 7
y z
2
E para grafos direcionados?

Começando no vértice S
Para cada vértice v em G Inicialização
v.dis = INFINITO
v.pre = VAZIO
s.dis = 0
T = todos os vértices de G
∞ ∞ iteração Vértices
visitados
s.dis t.dis x.dis y.dis z.dis
1
t x
0 {} ∞ ∞ ∞ ∞ ∞
10 9
∞ 2 3
s
4 6
5 7
y z
2
∞ ∞
remove u de T
d = u.dist + w(u,v)
Se d < v.dist
v.dist = d
v.pre = u
10 ∞ iteração Vértices
visitados
s.dis t.dis x.dis y.dis z.dis
1
t x
0 {} ∞ ∞ ∞ ∞ ∞
10 9 1 {s} 0 10 ∞ 5 ∞
0 2 3
s
4 6
5 7
y z
2
5 ∞
remove u de T
d = u.dist + w(u,v)
Se d < v.dist
v.dist = d
v.pre = u
8 14 iteração Vértices s.dis t.dis x.dis y.dis z.dis

1 visitados
t x
0 {} ∞ ∞ ∞ ∞ ∞
10 9 1 {s} 0 10 ∞ 5 ∞
0 2 3
s 2 {s,y} 0 8 14 5 7
4 6
5 7
y z
2
5 7
remove u de T
d = u.dist + w(u,v)
Se d < v.dist
v.dist = d
v.pre = u

1 visitados
t x
0 {} ∞ ∞ ∞ ∞ ∞
10 9 1 {s} 0 10 ∞ 5 ∞
0 2 3
s 2 {s,y} 0 8 14 5 7
4 6
3 {s,y,z} 0 8 13 5 7
5 7
y z
2
5 7
remove u de T
d = u.dist + w(u,v)
Se d < v.dist
v.dist = d
v.pre = u

1 visitados
t x
0 {} ∞ ∞ ∞ ∞ ∞
10 9 1 {s} 0 10 ∞ 5 ∞
0 2 3
s 2 {s,y} 0 8 14 5 7
4 6
3 {s,y,z} 0 8 13 5 7
5 7
4 {s,y,z,t} 0 8 9 5 7
y z
2
5 7
remove u de T
d = u.dist + w(u,v)
Se d < v.dist
v.dist = d
v.pre = u

1 visitados
t x
0 {} ∞ ∞ ∞ ∞ ∞
10 9 1 {s} 0 10 ∞ 5 ∞
0 2 3
s 2 {s,y} 0 8 14 5 7
4 6
3 {s,y,z} 0 8 13 5 7
5 7
4 {s,y,z,t} 0 8 9 5 7
5 {s,y,z,t,x} 0 8 9 5 7
y z
2
5 7
Floyd-Warshall: mínimos de todos os vértices
Caminhos entre todos os pares de vértices
O algoritmo de Floyd-Warshall encontra todos os caminhos

mínimos dos pares em um grafo.
Os pesos (ponderações) devem ser não-negativos.
Este algoritmo é útil em aplicações onde é necessária a

criação de uma matriz de caminhos mínimos ao invés de um
vetor.
O algoritmo, primeiramente modifica a matriz de adjacência:

Atribui infinito a todos os pares de vértices sem conexão,
exceto a diagonal principal.

Atribui infinito a todos os pares de vértices sem conexão
direta, exceto a diagonal principal.
1 1 2 3 4 5
2 3
5 1 1 0 5 0 2 0
2 5 0 1 0 0
1 4 5
2 10 3 0 1 0 1 0
4 2 0 1 0 10
5 0 0 0 10 0
Matriz simétrica com zeros na diagonal

(inicial)

Atribui infinito a todos os pares de vértices sem conexão
direta, exceto a diagonal principal.
1 1 2 3 4 5
2 3
5 1 1 0 5 ∞ 2 ∞
2 5 0 1 ∞ ∞
1 4 5
2 10 3 ∞ 1 0 1 ∞
4 2 ∞ 1 0 10
5 ∞ ∞ ∞ 10 0
Matriz simétrica com zeros na diagonal

(atribuindo infinitos)
A seguir, realiza comparações de distâncias entre todos os

pares de vértices.
Se encontrar um caminho menor, o algoritmo segue.

Se não encontrar nenhum, o algoritmo finaliza.
Algoritmo de Floyd-Warshall K=1
1 2 3 4 5 D[1,1] > D[1,1]+D[1,1] ? Não
1 0 5 ∞ 2 ∞ D[1,2] > D[1,1]+D[1,2] ? Não
D[1,3] > D[1,1]+D[1,3] ? Não
2 5 0 1 ∞ ∞ D[1,4] > D[1,1]+D[1,4] ? Não
D[1,5] > D[1,1]+D[1,5] ? Não
3 ∞ 1 0 1 ∞
4 2 ∞ 1 0 10
5 ∞ ∞ ∞ 10 0
for k de 1 até |V| // ordem de G ou qtd. vértices

for i de 1 até |V|
for j de 1 até |V|
dist[i][j] > dist[i][k] + dist[k][j]
1 2 3 4 5 D[1,1] > D[1,1]+D[1,1] ? Não
1 0 5 ∞ 2 ∞ D[1,2] > D[1,1]+D[1,2] ? Não
D[1,3] > D[1,1]+D[1,3] ? Não
2 5 0 1 ∞ ∞ D[1,4] > D[1,1]+D[1,4] ? Não
D[1,5] > D[1,1]+D[1,5] ? Não
3 ∞ 1 0 1 ∞
4 2 ∞ 1 0 10 D[2,1] > D[2,1]+D[1,1] ? Não
D[2,2] > D[2,1]+D[1,2] ? Não
5 ∞ ∞ ∞ 10 0
D[2,3] > D[2,1]+D[1,3] ? Não
D[2,4] > D[2,1]+D[1,4] ? SIM D[2,4]= 5+2=7
D[2,5] > D[2,1]+D[1,5] ? Não
1 2 3 4 5
1 0 5 ∞ 2 ∞ …
2 5 0 1 7 ∞ D[4,2] > D[4,1]+D[1,2] ? SIM D[4,2]= 2+5=7

3 ∞ 1 0 1 ∞
...
4 2 7 1 0 10
5 ∞ ∞ ∞ 10 0 Encontrou caminhos menores  segue

1 2 3 4 5 D[1,1] > D[1,2]+D[2,1] ? Não
1 0 5 ∞ 2 ∞ D[1,2] > D[1,2]+D[2,2] ? Não
D[1,3] > D[1,2]+D[2,3] ? SIM D[1,3]= 5+1=6
2 5 0 1 7 ∞ D[1,4] > D[1,2]+D[2,4] ? Não
3 ∞ 1 0 1 ∞ D[1,5] > D[1,2]+D[2,5] ? Não
4 2 7 1 0 10
5 ∞ ∞ ∞ 10 0 …
D[3,1] > D[3,2]+D[2,1] ? SIM D[3,1]= 1+5=6

1 2 3 4 5
...
1 0 5 6 2 ∞
2 5 0 1 7 ∞ Encontrou caminhos menores  segue
3 6 1 0 1 ∞
4 2 7 1 0 10
5 ∞ ∞ ∞ 10 0
1 2 3 4 5 D[1,1] > D[1,3]+D[3,1] ? Não
1 0 5 6 2 ∞ D[1,2] > D[1,3]+D[3,2] ? Não
D[1,3] > D[1,3]+D[3,3] ? Não
2 5 0 1 7 ∞ D[1,4] > D[1,3]+D[3,4] ? Não
D[1,5] > D[1,3]+D[3,5] ? Não
3 6 1 0 1 ∞
4 2 7 1 0 10 D[2,1] > D[2,3]+D[3,1] ? Não
D[2,2] > D[2,3]+D[3,2] ? Não
5 ∞ ∞ ∞ 10 0
D[2,3] > D[2,3]+D[3,3] ? Não
D[2,4] > D[2,3]+D[3,4] ? SIM D[2,4]=1+1=2
D[2,5] > D[2,3]+D[3,5] ? Não
1 2 3 4 5
1 0 5 6 2 ∞ …
2 5 0 1 2 ∞ D[4,2] > D[4,3]+D[3,4] ? SIM D[4,2]=1+1=2

3 6 1 0 1 ∞
...
4 2 2 1 0 10
5 ∞ ∞ ∞ 10 0 Encontrou caminhos menores  segue

1 2 3 4 5 …
1 0 5 6 2 ∞ D[1,2] > D[1,4]+D[4,2] ? SIM D[1,2]=2+2=4
D[1,3] > D[1,4]+D[4,3] ? SIM D[1,3]=2+1=3
2 5 0 1 2 ∞ D[1,5] > D[1,4]+D[4,5] ? SIM D[1,5]=2+10=12
3 6 1 0 1 ∞ ...
D[2,1] > D[2,4]+D[4,1] ? SIM D[2,1]=2+2=4
4 2 2 1 0 10
D[2,5] > D[2,4]+D[4,5] ? SIM D[2,5]=2+10=12
5 ∞ ∞ ∞ 10 0 …
D[3,1] > D[3,4]+D[4,1] ? SIM D[3,1]=1+2=3
D[3,5] > D[3,4]+D[4,5] ? SIM D[3,5]=1+10=11
1 2 3 4 5
…
1 0 4 3 2 12
2 4 0 1 2 12 D[5,1] > D[5,4]+D[4,1] ? SIM D[5,1]=10+2=12

3 3 1 0 1 11 D[5,2] > D[5,4]+D[4,2] ? SIM D[5,2]=10+2=12
D[5,3] > D[5,4]+D[4,3] ? SIM D[5,3]=10+1=11
4 2 2 1 0 10
5 12 12 11 10 0 Encontrou caminhos menores  segue

1 2 3 4 5
1 0 4 3 2 12 Não houveram modificações, o algoritmo finaliza
2 4 0 1 2 12
3 3 1 0 1 11
4 2 2 1 0 10
5 12 12 11 10 0
Algoritmo de Floyd-Warshall
1 2 3 4 5
1
1 0 4 3 2 12 2 3
2 4 0 1 2 12 5 1
3 3 1 0 1 11
1 4 5
2 1 0 10 2 10
4 2
5 12 12 11 10 0
Referências
Para mais informações sobre os caminhos mínimos:
Dijkstra
https://www.ime.usp.br/~pf/algoritmos_para_grafos/aulas/dijkstra.html
Floyd-Warshall All-Pairs Shortest Pairs Algorithm

http://www.pms.ifi.lmu.de/lehre/compgeometry/Gosper/shortest_path/shortest_path.html

CR Modulo4

Enviado por

Direitos autorais:

Formatos disponíveis

CR Modulo4

Enviado por

Dados do documento

Título original

Direitos autorais

Formatos disponíveis

Compartilhar este documento

Compartilhar ou incorporar documento

Opções de compartilhamento

Você considera este documento útil?

Este conteúdo é inapropriado?

Direitos autorais:

Formatos disponíveis

CR Modulo4

Enviado por

Direitos autorais:

Formatos disponíveis

BC0506 - Comunicação e Redes

Algoritmos de caminhos mínimos

Existem diversos caminhos que podem ser percorridos para

Qual seria (e como encontrar) o melhor caminho?

A busca em largura não fornece isso?

Reparem que em um grafo ponderado (com valores nas

Caminho com menos arestas:

Modelar o problema através de grafos.

Modelar o problema através de grafos.

No grafo, um caminho C é mínimo se não existe outro

Lembrando que a distância entre s e t é o comprimento do

Se não existe caminho algúm entre s e t, então a distância

Grafos não-ponderados (distância usa a qtde. de arestas)

Grafos ponderados (distância usa a ponderação das arestas)

Muitas aplicações associam

Grafos ponderados (distância usa a ponderação das arestas)

Grafos ponderados (distância usa a ponderação das arestas)

Grafos ponderados (distância usa a ponderação das arestas)

Para a busca de caminhos mínimos em grafos

Dado um vértice s de um grafo ponderado, encontrar para

Todos os algoritmos para esses problemas exploram a

sendo d(i,j) a distância do vértice i ao vértice j.

Algoritmo eficiente para a obtenção do caminho mínimo em

Criado pelo cientista da computação Edsger Dijkstra em 1956

iteração Vértices a.dis b.dis c.dis d.dis e.dis

iteração Vértices a.dis b.dis c.dis d.dis e.dis

iteração Vértices a.dis b.dis c.dis d.dis e.dis

iteração Vértices a.dis b.dis c.dis d.dis e.dis

iteração Vértices a.dis b.dis c.dis d.dis e.dis

iteração Vértices a.dis b.dis c.dis d.dis e.dis

Enquanto houveram vértices não visitados:

iteração Vértices a.dis b.dis c.dis d.dis e.dis

iteração Vértices a.dis b.dis c.dis d.dis e.dis

iteração Vértices a.dis b.dis c.dis d.dis e.dis

iteração Vértices a.dis b.dis c.dis d.dis e.dis

iteração Vértices a.dis b.dis c.dis d.dis e.dis

E para grafos direcionados?

8 14 iteração Vértices s.dis t.dis x.dis y.dis z.dis

8 13 iteração Vértices s.dis t.dis x.dis y.dis z.dis

8 9 iteração Vértices s.dis t.dis x.dis y.dis z.dis

8 9 iteração Vértices s.dis t.dis x.dis y.dis z.dis

O algoritmo de Floyd-Warshall encontra todos os caminhos

Os pesos (ponderações) devem ser não-negativos.

Este algoritmo é útil em aplicações onde é necessária a

O algoritmo, primeiramente modifica a matriz de adjacência:

O algoritmo, primeiramente modifica a matriz de adjacência:

Matriz simétrica com zeros na diagonal

O algoritmo, primeiramente modifica a matriz de adjacência:

Matriz simétrica com zeros na diagonal

A seguir, realiza comparações de distâncias entre todos os

Se encontrar um caminho menor, o algoritmo segue.

for k de 1 até |V| // ordem de G ou qtd. vértices

2 5 0 1 7 ∞ D[4,2] > D[4,1]+D[1,2] ? SIM D[4,2]= 2+5=7

5 ∞ ∞ ∞ 10 0 Encontrou caminhos menores  segue

D[3,1] > D[3,2]+D[2,1] ? SIM D[3,1]= 1+5=6

2 5 0 1 2 ∞ D[4,2] > D[4,3]+D[3,4] ? SIM D[4,2]=1+1=2

5 ∞ ∞ ∞ 10 0 Encontrou caminhos menores  segue

2 4 0 1 2 12 D[5,1] > D[5,4]+D[4,1] ? SIM D[5,1]=10+2=12

5 12 12 11 10 0 Encontrou caminhos menores  segue