Algoritmos em Grafos
CAMINHOS MAIS CURTOS
Algoritmos em Grafos
2
Caminhos mais Curtos
Dados: grafo G=(V,A) orientado e
distância cij associada ao arco (i,j)  A.
Problema: Obter o caminho mais curto entre dois nós s e t.
O comprimento de um caminho é igual à soma dos
comprimentos (distâncias) dos arcos que formam o caminho.
A “distância” ou “comprimento” de um arco pode ter diversas
interpretações dependendo da aplicação: custos, distâncias, consumo
de combustível, etc.
Exemplo 1: Dado um mapa rodoviário, determinar a rota mais
curta de uma cidade a outra.
(rota mais rápida,
rota com menor consumo de combustível, ...)
Algoritmos em Grafos
3
Caminhos mais Curtos
Exemplo 2: Construção de uma estrada entre duas cidades A e
K. O grafo abaixo representa os diversos trechos possíveis e o
custo de construção de cada um. Determinar o trajeto ótimo
cujo custo de construção seja mínimo (corresponde a achar o
caminho mais curto de A a K em relação a estes custos).
B
2
8
5
C
D
Solução:
4
4
F
I
2
4
4
7
H
4
4
5
A
E
6
5
K
2
4
2
G
4
J
A–D–G–I–K
custo = 7 + 2 + 2 + 5 = 16
Algoritmos em Grafos
4
Caminhos mais Curtos
Condição de existência:
Caminho de i a j contendo um circuito w:
k
j
i
w
Comprimento do caminho =
comprimento (i  k) +
comprimento (w) +
comprimento (k  j)
Qual é o comprimento do caminho mais curto de i a j se o
comprimento do circuito w é negativo?
Algoritmos em Grafos
5
Caminhos mais Curtos
Condição de existência:
não há circuitos de comprimento negativo.
A solução ótima (caminho mais curto) sempre será um
caminho elementar (sem circuito).
Algoritmos em Grafos
6
Caminhos mais Curtos
Caminho mais curto:
- De um nó a outro
- De um nó a todos os demais
- Entre todos os pares de nós de um grafo
Algoritmos em Grafos
7
Caminhos mais Curtos
Caminho mais curto do nó 1 a cada nó do grafo G=(V,A)
Hipótese: todas as distâncias cij são positivas:
cij ≥ 0, (i,j)  A
Algoritmo de Moore-Dijkstra (1957-1959)
*(i) = comprimento do caminho mais curto do nó 1 ao nó i
Em especial, *(1)=0 (distâncias positivas).
Algoritmo com n-1 iterações
No início de cada iteração, o conjunto V de nós está particionado
em dois subconjuntos S e S, com o nó 1 em S.
S S 
S  S V
Algoritmos em Grafos
8
Caminhos mais Curtos
Cada nó i  V possui um rótulo (i ), que verifica a seguinte
propriedade:
Se i  S   (i )   * (i )
 (i )  min (k )  cki 
Se i  S   (i )   * (i )
kS
 (i ), i  S , dá o valor do caminho mais curto de 1 a i sob a
restrição de que todos os nós utilizados (exceto o próprio i )
pertençam a S.
 (a )
a
 (b )
1
cai
 (i )
i
b
cbi
 (c ) c
ci
c
S
S
Algoritmos em Grafos
9
Caminhos mais Curtos
Teorema: Seja o nó j  S tal que  ( j )  min  (i ).
i S

*
(
j
)


(
j
)
Então
, isto é, o comprimento do caminho
mais curto do nó 1 ao nó j é igual a  ( j ) .
Demonstração:
Por construção, certamente existe um caminho de 1 até j com
comprimento (j).
Suponhamos que exista outro caminho de 1 a j de comprimento
menor do que (j).
Dividamos este caminho em duas partes:
- P1 é a parte inicial, do nó 1 ao nó L, onde L é o primeiro nó de S
encontrado
- P2 é a parte final, do nó L ao nó j
Algoritmos em Grafos
10
Caminhos mais Curtos
comprimento de P1 ≥ (L) ≥ (j)
comprimento de P2 ≥ 0
Logo, o comprimento de P1 + P2 ≥ (j).
Algoritmos em Grafos
11
Caminhos mais Curtos
Algoritmo de Moore-Dijkstra
Inicializar S  {2,3,...,n},
S  {1},
(1) 0,
(j) c1j se j1+
+ caso contrário
Enquanto S   faça
Selecionar jS tal que (j)= miniS{(i)}
S  S – {j}
Para iS e ij+ faça
(i)  min{(i), (j)+cji}
fim_enquanto
O algoritmo constrói progressivamente o conjunto dos nós mais
próximos de 1.
 Construção de uma arborescência com raiz em 1 que define os
caminhos mais curtos do nó 1 a cada nó do grafo.
Algoritmos em Grafos
12
Caminhos mais Curtos
Exemplo:
S = {1}
S = {2,3,4,5,6}
4
4
5
2
2
5
7
1
1
5
1
2
3
3
6
7
(1) = 0
(2) = 7
(3) = 1
(4) = (5) = (6) = +
ITERAÇÃO 1
4
4
5
2
2
j=3
S = {2,4,5,6}
5
7
*(1) = 0
1
1
5
1
2
3
3
*(3) = 1
6
7
(2) = min{7, 1+5} = 6
(5) = min{, 1+2} = 3
(6) = min{, 1+7} = 8
Algoritmos em Grafos
13
Caminhos mais Curtos
4
4
5
2
2
*(5) = 3
5
j=5
S = {2,4,6}
7
*(1) = 0
1
1
5
1
2
3
3
6
ITERAÇÃO 3
4
4
5
2
2
*(5) = 3
5
j=2
S = {4,6}
7
*(1) = 0
1
1
5
1
2
3
3
*(3) = 1
(2) = min{6, 3+2} = 5
(4) = min{, 3+5} = 8
7
*(3) = 1
*(2) = 5
ITERAÇÃO 2
6
(4) = min{8, 5+4} = 8
(6) = min{, 5+1} = 6
7
Algoritmos em Grafos
14
Caminhos mais Curtos
4
*(2) = 5
4
5
2
2
*(5) = 3
5
j=6
S = {4}
7
*(1) = 0
1
1
5
1
2
3
3
*(6) = 6
*(4) = 8
ITERAÇÃO 5
4
4
5
2
2
*(5) = 3
5
j=4
S={}
7
*(1) = 0
1
1
5
1
(4) = 8
6
7
*(3) = 1
*(2) = 5
ITERAÇÃO 4
2
3
3
*(3) = 1
6
7
*(6) = 6
Algoritmos em Grafos
15
Caminhos mais Curtos
3
2
3
5
6
4
1
1
5
2
2
2
3
4
7
3

Iteração
1
3
4
Início
1
2
3
4
5
6
1
0
0
0
0
0
0
0
2
4
4
4
4
4
4
4
3
2
2
2
2
2
2
2
4

5
5
5
5
5
5
5

4
4
4
4
4
4
6


7
7
7
7
7
7


7
7
7
7
7
nó
Algoritmos em Grafos
16
Caminhos mais Curtos
Número de operações (tempo): O(n2)
n-1 iterações, cada iteração busca o mínimo em uma lista com
até n-1 elementos (vetor )
Caminho mais curto do nó 1:
 ao nó j
 a todos os nós
Mesma complexidade, mas critérios de parada diferentes.
Algoritmos em Grafos
17