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?

Caminhos mínimos - Motivação

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
Caminhos mínimos - Motivação

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.
Caminhos mínimos - Motivação

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
Caminhos mínimos - Motivação

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.
Caminhos mínimos - Motivação

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.
Caminhos mínimos - Motivação

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

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

h
1
1
b c Distância entre:
h,k = Infinito
5 7 1
h,e = ?
a d f
2 10

3 7
e k
Distância

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

h
1
1
b c Distância entre:
h,k = Infinito
5 7 1
h,e = 8
a d f
2 10

3 7
e k
Distância

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

h
1
1
b c Distância entre:
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.
Algoritmo de Dijkstra

Começando no vértice a

a
1 10

3
b e

5 1 6

c d
2
Algoritmo de Dijkstra

iteração Vértices [Link] [Link] [Link] [Link] [Link]

∞ visitados

a 0 {} ∞ ∞ ∞ ∞ ∞
1 10
∞ 3 ∞
b e

5 1 6

c d
∞ 2 ∞
Algoritmo de Dijkstra

iteração Vértices [Link] [Link] [Link] [Link] [Link]

0 visitados

a 0 {} ∞ ∞ ∞ ∞ ∞
1 10 1 {a} 0 1 ∞ 3 10
1 3 10
b e

5 1 6

c d
∞ 2 3
Algoritmo de Dijkstra

iteração Vértices [Link] [Link] [Link] [Link] [Link]

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
Algoritmo de Dijkstra

iteração Vértices [Link] [Link] [Link] [Link] [Link]

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
Algoritmo de Dijkstra

iteração Vértices [Link] [Link] [Link] [Link] [Link]

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
Algoritmo de Dijkstra

iteração Vértices [Link] [Link] [Link] [Link] [Link]

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
Algoritmo de Dijkstra

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).
Algoritmo de Dijkstra

Começando no vértice b

a
2 4

3
b e
6
7
3 3

c d
2
Algoritmo de Dijkstra

∞
iteração Vértices [Link] [Link] [Link] [Link] [Link]
visitados

a 0 {} ∞ ∞ ∞ ∞ ∞
2 4
∞
b
6
3
e ∞
7
3 3

c d
∞ 2 ∞
Algoritmo de Dijkstra

iteração Vértices [Link] [Link] [Link] [Link] [Link]

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
Algoritmo de Dijkstra

iteração Vértices [Link] [Link] [Link] [Link] [Link]

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
Algoritmo de Dijkstra

iteração Vértices [Link] [Link] [Link] [Link] [Link]

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
Algoritmo de Dijkstra

iteração Vértices [Link] [Link] [Link] [Link] [Link]

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
Algoritmo de Dijkstra

iteração Vértices [Link] [Link] [Link] [Link] [Link]

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
Algoritmo de Dijkstra

Dijkstra(G,s,w)
Para cada vértice v em G Inicialização
[Link] = INFINITO
[Link] = VAZIO
[Link] = 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 = [Link] + w(u,v)
Se d < [Link]
[Link] = d
[Link] = u
Algoritmo de Dijkstra

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
Algoritmo de Dijkstra
Para cada vértice v em G Inicialização
[Link] = INFINITO
[Link] = VAZIO
[Link] = 0
T = todos os vértices de G

∞ ∞ iteração Vértices
visitados
[Link] [Link] [Link] [Link] [Link]
1
t x
0 {} ∞ ∞ ∞ ∞ ∞
10 9
∞ 2 3
s
4 6

5 7

y z
2
∞ ∞
Algoritmo de Dijkstra
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 = [Link] + w(u,v)
Se d < [Link]
[Link] = d
[Link] = u

10 ∞ iteração Vértices
visitados
[Link] [Link] [Link] [Link] [Link]
1
t x
0 {} ∞ ∞ ∞ ∞ ∞
10 9 1 {s} 0 10 ∞ 5 ∞
0 2 3
s
4 6

5 7

y z
2
5 ∞
Algoritmo de Dijkstra
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 = [Link] + w(u,v)
Se d < [Link]
[Link] = d
[Link] = u

8 14 iteração Vértices [Link] [Link] [Link] [Link] [Link]

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
Algoritmo de Dijkstra
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 = [Link] + w(u,v)
Se d < [Link]
[Link] = d
[Link] = u

8 13 iteração Vértices [Link] [Link] [Link] [Link] [Link]

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
Algoritmo de Dijkstra
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 = [Link] + w(u,v)
Se d < [Link]
[Link] = d
[Link] = u

8 9 iteração Vértices [Link] [Link] [Link] [Link] [Link]

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
Algoritmo de Dijkstra
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 = [Link] + w(u,v)
Se d < [Link]
[Link] = d
[Link] = u

8 9 iteração Vértices [Link] [Link] [Link] [Link] [Link]

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.
Caminhos entre todos os pares de vértices

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

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)
Caminhos entre todos os pares de vértices

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

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)
Caminhos entre todos os pares de vértices

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]
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 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

Algoritmo de Floyd-Warshall K=2
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
Algoritmo de Floyd-Warshall K=3
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

Algoritmo de Floyd-Warshall K=4
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

Algoritmo de Floyd-Warshall K=5
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
[Link]

Floyd-Warshall All-Pairs Shortest Pairs Algorithm

[Link]