Algoritmos em Grafos
Celso C. Ribeiro
Caroline T. Rocha
PARTE 2: 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 )
Se i  S   (i )   * (i )
 (i )  min  (k )  c ki 
k S
k Γ i
 (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): ~ 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.
Distâncias negativas:
3
3
1
-8
10
2
Caminho mais curto de 1 a 3?
2
Resultado do algoritmo?
3
Por que?
Algoritmos em Grafos
17
Caminhos mais Curtos
Extensão do algoritmo de Moore-Dijkstra para o caso
com distâncias negativas (mas sem ciclos negativos)
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j+ faça
Calcular *  (j)+ cji
Se * < (i) então
S  S  {i}
(i)  *
fim-se
fim-para
fim-enquanto
Algoritmos em Grafos
18
Caminhos mais Curtos
3
2
3
5
6
4
1
1
2
-3
2
-2
3
1
3
4
7
3
4
S=X
2 3
6 X
7 X
3 X
5
X 4X 5X X

Iteração
Início
nó
1
2
3
4
5
6
7
8
1
0
0
0
0
0
0
0
0
0
2
4
4
4
4
4
4
4
4
4
3
2
2
2
1
1
1
1
1
1
4

5
5
5
4
4
4
4
4
5

4
4
4
3
3
2
2
2
6


7
7
7
6
6
5
5
7


7
7
7
6
6
5
5
Algoritmos em Grafos
19
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
20
Caminhos mais Curtos
Caminho mais curto entre todos os pares de nós de um grafo
Dados:
Grafo G=(V, A) orientado, |V | = n.
Não há circuitos negativos.
c = {cij}, j = 1,...,n, i = 1,...,n
cij ≥ 0
cii = 0
cij = +, (i, j )  A
Ak(i, j ) = valor do caminho mais curto de i a j podendo
usar apenas nós numerados de 1 a k como nós
intermediários.
Algoritmos em Grafos
21
Caminhos mais Curtos
A0(i, j ) = cij : caminho mais curto de i a j usando no máximo o
nó “0” (que não existe) como nó intermediário
(caminho mais curto de i a j sem nós
intermediários)
Ak(i, j ) : pode usar o nó k ou não.
Ak+1(i, j ) : pode usar o nó k+1 ou não.
A0  A1
A1  A2
...
An-1  An
An(i, j ) = valor do caminho mais curto
de i a j podendo usar
qualquer nó de 1 a n como
nó intermediário.
Algoritmos em Grafos
22
Caminhos mais Curtos
Se Ak+1(i, j ) não usa o nó k+1 como intermediário, então:
Ak+1(i, j ) = Ak(i, j )
Se Ak+1(i, j ) usa o nó k+1 como intermediário, então:
Ak+1(i, j ) = Ak(i, k+1) + Ak(k+1, j )
Ak+1(i, j ) = min { Ak(i, j ), Ak(i, k+1) + Ak(k+1, j ) }
Algoritmos em Grafos
23
Caminhos mais Curtos
Algoritmo de Floyd:
Para i = 1,...,n faça
Para j = 1,...,n faça
A0(i,j)  cij
fim-para
fim-para
Para k = 1,...,n faça
Para i = 1,...,n faça
Para j = 1,...,n faça
Ak(i,j)  min{Ak-1(i,j),
Ak-1(i,k) + Ak-1(k,j)}
fim-para
fim-para
fim-para
Algoritmos em Grafos
24
Caminhos mais Curtos
Exemplo:
6
1
2
4
3
C=
11
2
0
4
11
6
0
2
3
+∞
0
A0 =
0
4
11
6
0
2
3
+∞
0
0
4
6
5
0
2
3
7
0
3
A1 =
0
4
11
6
0
2
3
7
0
A2 =
0
4
6
6
0
2
3
7
0
A3 =
Algoritmos em Grafos
25
Caminhos mais Curtos
Algoritmo de Dijkstra: número de operações (tempo) ~ n2
n-1 iterações, cada iteração busca o mínimo em uma lista com
até n-1 elementos (vetor )
Algoritmo de Floyd: número de operações (tempo) ~ n3
Três comandos for de 1 até n um dentro do outro
Ou seja, o problema de calcular os caminhos mais curtos entre
todos os pares de nós pode ser resolvido com a mesma
eficiência aplicando-se n vezes o algoritmo de Dijkstra, uma vez
a partir de cada nó inicial.
Algoritmos em Grafos
26