Caminhos mínimos

MC558 - Projeto e Análise de

Algoritmos II

11
09/24

Santiago Valdés Ravelo

https://ic.unicamp.br/~santiago/
[email protected]
“Às vezes, a coisa mais produtiva que você pode fazer é relaxar.”

Mark Black
Caminhos mínimos com
uma origem
 Caminhos mínimos com uma origem

Problema do Caminho Mínimo

Considere um par (G, w ) em que:

I G é um grafo direcionado.

I w associa um peso w (u, v ) para cada aresta (u, v).

Estamos interessados nos seguintes problemas:

1. Problema do caminho mínimo entre dois vértices:

Dados s e t, encontrar um caminho de peso mínimo de s a t.

2. Problema dos caminhos mínimos com mesma origem:

Dado s, encontrar um caminho de peso mínimo de s a v para
TODO vértice v de G.
 Caminhos mínimos com uma origem

Exemplo: grafo direcionado acíclico

6 4

5 2 7 −1 −2
a b c d e f
3 4
2

v a b c d e f
dist(b, v ) ∞ 0 2 6 5 3
 Caminhos mínimos com uma origem

Exemplo: grafo direcionado sem arestas negativas

1
a f
10 2
2 3 9 4 4
b e

5 2 5
c d

v a b c d e f
dist(b, v ) 8 0 5 7 11 9
 Caminhos mínimos com uma origem

Exemplo: grafo direcionado com arestas negativas

5 −4
a −2 e
6

b 8 −3 7

7
c d
9

v a b c d e
dist(b, v ) 2 0 7 −2 4
 Caminhos mínimos com uma origem

Representando caminhos mínimos

A saída é similar à da busca em largura a partir de s:

I Para cada v ∈ V[G], associamos um PREDECESSOR π[v].

I O vetor π induz uma ÁRVORE DE CAMINHOS

MÍNIMOS com raiz em s.

I Um caminho de s a v na árvore é um caminho mínimo

de s a v no grafo G.
 Caminhos mínimos com uma origem

Definição

Problema (Caminhos mínimos com mesma origem)

Entrada: Um grafo direcionado G = (V, E), com peso w nas
arestas, sem ciclos de peso negativo e um vértice de origem s.

Saída: Um vetor d com d[v] = dist(s,v) para v ∈ V e um vetor π

definindo uma ÁRVORE DE CAMINHOS MÍNIMOS.
 Caminhos mínimos com uma origem

Subestrutura ótima de caminhos mínimos

Teorema
Seja (G, w ) um grafo direcionado SEM CICLOS NEGATIVOS e
seja
P = (v1 , v2 , . . . , vk )
um caminho mínimo de v1 a vk . Então para quaisquer índices i, j
com 1 ≤ i ≤ j ≤ k, o subcaminho

Pij = (vi , vi+1 , . . . , vj )

é um caminho mínimo de vi a vj .
 Caminhos mínimos com uma origem

Subestrutura ótima de caminhos mínimos

A subestrutura ótima NÃO vale se o grafo tiver

CICLOS NEGATIVOS:

−4
1
a b 1 c

I (a, b, c) é um caminho mínimo de a a c com peso 1 + 1 = 2.

I Mas, (a,b) NÃO é um caminho mínimo de a a b.

I (a,c,b) é um caminho mínimo de a a b com peso 3 − 4 = −1.

 Caminhos mínimos com uma origem

Algoritmos baseados em relaxação

Veremos algoritmos com as seguintes características:

1. Inicializam d e π com uma sub-rotina
Initialize-Single-Source.
2. Alteram d e π apenas com uma sub-rotina Relax.

Esses algoritmos mantêm algumas invariantes:

I Existe um caminho de s a v com peso d[v].
I Esse caminho pode ser recuperado por meio π.
I Assim, d[v] é sempre MAIOR OU IGUAL a dist(s,v).
I Queremos que no final valha d[v] = dist(s,v).
 Caminhos mínimos com uma origem

Inicialização

Algoritmo: Initialize-Single-Source(G, s)
1 para cada v ∈ V [G]
2 d[v ] ← ∞
3 π[v ] ← NIL
4 d[s] ← 0
 Caminhos mínimos com uma origem

Relaxação

Tenta melhorar a estimativa d[v] examinando (u,v).

d[a] = 5 d[b] = 9 d[a] = 5 d[b] = 6
2 2
a b a b

Relax Relax

d[a] = 5 d[b] = 7 d[a] = 5 d[b] = 6

2 2
a b a b

Algoritmo: Relax(u, v , w )
1 se d[v ] > d[u] + w (u, v )
2 d[v ] ← d[u] + w (u, v )
3 π[v ] ← u
 Caminhos mínimos com uma origem

Relaxação dos vizinhos

Em cada iteração o algoritmo seleciona um vértice u e para cada

vizinho v de u aplica Relax(u,v, w ).

b d[b] = 9 b d[b] = 7
2 2
1 1
d[a] = 5 a c d[c] = 4 d[a] = 5 a c d[c] = 4
20 20

d d[d] = ∞ d d[d] = 25
 Caminhos mínimos com uma origem

Casos do problema de caminhos mínimos

Veremos três algoritmos baseados em relaxação para tipos de

subcasos diferentes do Problema de caminhos mínimos:

1. APLICAÇÃO DE ORDENAÇÃO TOPOLÓGICA: G é

acíclico.

2. ALGORITMO DE DIJKSTRA: (G, w ) não tem arestas de

peso negativo.

3. ALGORITMO DE BELLMAN-FORD: (G, w ) pode ter

arestas de peso negativo, mas não contém ciclos negativos.
Caminhos mínimos em
grafos acíclicos
 Caminhos mínimos em grafos acíclicos

Caminhos mínimos em grafos acíclicos

Problema
Entrada: Um grafo direcionado acíclico G = (V, E), uma função
de peso w nas arestas e um vértice origem s.

Saída: Um vetor d com d[v] = dist(s,v) para v ∈ V e um vetor π

definindo uma ÁRVORE DE CAMINHOS MÍNIMOS.
 Caminhos mínimos em grafos acíclicos

Exemplo

6 4

5 2 7 −1 −2
a b c d e f
3 4
2

a b c d e f
d ∞ 0 ∞
2 ∞
6 ∞
5 ∞
6 3
4
 Caminhos mínimos em grafos acíclicos

Algoritmo

Algoritmo: Dag-Shortest-Paths(G, w , s)
1 ordene topologicamente os vértices de G
2 Initialize-Single-Source(G, s)
3 para cada u na ordem topológica
4 para cada v ∈ Adj[u]
5 Relax(u, v , w )

6 devolva d, π

Linha(s) Tempo total

1 O(V + E )
2 O(V )
3-5 O(V + E )

Complexidade de Dag-Shortest-Paths: O(V + E ).

 Caminhos mínimos em grafos acíclicos

Correção

I Há diversas estratégias para demonstrar que

Dag-Shortest-Paths esteja correto.

I Vamos demonstrar algumas propriedades que valem porque o

algoritmo é baseado em relaxação.

I Essas propriedades também serão úteis para analisar os outros

algoritmos depois.
 Caminhos mínimos em grafos acíclicos

Propriedade de algoritmos baseados em relaxação

Ao longo de um algoritmo baseado em relaxação sempre vale:
I Limite superior: Vale d[v] ≥ dist(s,v) e, tão logo d[v] alcança dist(s,v),
nunca mais muda.
I Inexistência de caminho: Se não existe caminho de s a v, então
d[v] = ∞.
I Subgrafo de predecessores: Se d[v] < ∞, então o subgrafo dos
predecessores induzido por π é um caminho de peso d[v].
I Convergência: Se p é um caminho mínimo de s até v terminando com a
aresta (u,v) e d[u] = dist(s,u), então ao relaxar (u,v), d[v] = dist(s,v),
que nunca mais muda.
I Relaxamento de caminho: Se p = (v0 , v1 , . . . , vk ) é um caminho mínimo
de s = v0 a vk e relaxamos as arestas de p na ordem
(v0 , v1 ), (v1 , v2 ), . . . , (vk−1 , vk ), então d[vk ] = dist(s, vk ).
A propriedade vale mesmo se tivermos realizado quaisquer outras
relaxações durante a execução.
 Caminhos mínimos em grafos acíclicos

Correção de Dag-Shortest-Paths

I Seja v um vértice e suponha que p = (v0 , v1 , . . . , vk ) é um

caminho mínimo de s = v0 a v = vk .
I Como v0 , v1 , . . . , vk aparecem em ordem na ordenação
topológica, as arestas (v0 , v1 ), . . . , (vk−1 , vk ) são relaxadas
em ordem.
I Logo, pela propriedade do Relaxamento de caminho, o
algoritmo computa corretamente d[v] = dist(s,v) para cada
v ∈ V.

Também é fácil ver que π define uma árvore de caminhos mínimos.

Por quê?
 Caminhos mínimos em grafos acíclicos

Perguntas

Vamos fazer alguns exercícios?

 Caminhos mínimos em grafos acíclicos

Exercício 1

Como se resolve o problema de encontrar um caminho de peso

MÁXIMO de s a t em um grafo direcionado acíclico (G, w )?
 Caminhos mínimos em grafos acíclicos

Exercício 2

Como se resolve o problema do caminho mínimo de s a t em

TEMPO LINEAR para um grafo direcionado em que todas as
arestas têm o mesmo peso C > 0?
Caminhos mínimos
MC558 - Projeto e Análise de
Algoritmos II

11
09/24

Santiago Valdés Ravelo

https://ic.unicamp.br/~santiago/
[email protected]