Algoritmos de Caminho Mínimo
em Grafos
CC/EC/Mestrado
Teoria dos Grafos
CAMINHOS MAIS CURTOS
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, ...)
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
2
4
2
G
4
J
A–D–G–I–K
custo = 7 + 2 + 2 + 5 = 16
K
Caminhos mais Curtos
•
Condição de existência:
Caminho de i a j contendo um ciclo 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 ciclo w é negativo?
Caminhos mais Curtos
Condição de existência:
não há ciclos de comprimento negativo.
A solução ótima (caminho mais curto) sempre será um
caminho elementar (sem ciclos).
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
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.
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 )
min k ∈S,k∈ Γ (k ) {π( k )+c ki }
π (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
cai
π (b)
1
π (i )
i
b
cbi
π (c) c
ci
c
S
̄S
Caminhos mais Curtos
j ∈ S̄ tal que π ( j ) =mini ∈ S̄ π ( .i )
Teorema: Seja o nó
Então π∗ ( j )=π ( j) , isto é, o comprimento do caminho
π( j)
mais curto do nó 1 ao nó j é igual a
.
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
Caminhos mais Curtos
comprimento de P1 ≥ (L) ≥ (j)
comprimento de P2 ≥ 0
Logo, o comprimento de P1 + P2 ≥ (j).
Algoritmo de Dijkstra
•
Resolve o problema com um vértice-fonte
em grafos cujas arestas tenham peso
maior ou igual a zero. Este algoritmo é
capaz de determinar o caminho mínimo, a
partir de um vértice inicial v, para todos os
outros vértices do grafo.
CC/EC/Mestrado
Teoria dos Grafos
Algoritmo de Dijkstra
vINI = vértice inicial
d(vINI, vINI) = 0
d(vINI, i) = INFINITO, i, i  V – {vINI}
fechado = 
aberto = V
anterior(i) = 0, i, i  V
enquanto(aberto ≠ ) {
k = vértice pertencente a aberto, mais próximo do vértice inicial
fechado = fechado  k; aberto = aberto – k;
para cada vizinho i de k que está em aberto faça{
custo = min{d(vINI, i), d(vINI,k) + c(k,i)}
se (custo < d(vINI, i)) então
d(vINI, i) = custo; anterior(i) = k
}
}
CC/EC/Mestrado
Teoria dos Grafos
Execução
7. 2 é o vértice 13.
de menor
6 é o custo;
vértice de menor custo;
fechado = fechado+{6}
fechado = fechado+{2}
2. inicializando os custos
8. examinando os vértices vizinhos ao
14. fim alcançado
2
3. atualizando o conjunto
fechado
9. 4 é o vértice de menor custo;
4. examinando os vértices
ao
fechado vizinhos
= fechado+{4}
1 que estão em aberto
10. examinando os vértices vizinhos
5. 3 é o vértice de
custo;
ao menor
4
fechado = fechado+{3}
11. 5 é o vértice de menor custo;
6. examinando os fechado
vértices= vizinhos
ao
fechado+{5}
3
12. examinando os vértices vizinhos
ao 5
1. o grafo inicial
fim do algoritmo
CC/EC/Mestrado
Teoria dos Grafos
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
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?
Resultado do algoritmo?
Porque?
2
3