Algoritmo de

Bellman-Ford MC558 - Projeto e Análise de

Algoritmos II

13
09/24

Santiago Valdés Ravelo

[Link]
ravelo@[Link]
“A menor distância entre pontos é uma linha reta.”

Arquimedes
Aulas anteriores
 Aulas anteriores

Representando caminhos mínimos

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.
 Aulas anteriores

Inicialização

Algoritmo: Initialize-Single-Source(G, s)
1 para cada v ∈ V [G]
2 d[v ] ← ∞
3 π[v ] ← NIL
4 d[s] ← 0
 Aulas anteriores

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
 Aulas anteriores

Algoritmos baseados em relaxação

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).
 Aulas anteriores

Propriedade de algoritmos baseados em relaxação

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.
Algoritmo de
Bellman-Ford
 Algoritmo de Bellman-Ford

Arestas vs ciclos de peso negativo

I O algoritmo de Dijkstra resolve o Problema dos Caminhos

Mínimos quando (G, w ) NÃO TEM ARESTAS DE PESO
NEGATIVO.

I Quando (G, w ) possui arestas negativas, o algoritmo de

Dijkstra não funciona.

I Uma das dificuldades com arestas negativas é a possível

existência de CICLOS DE PESO NEGATIVO ou
simplesmente ciclos negativos.
 Algoritmo de Bellman-Ford

Ciclos negativos — uma dificuldade

I O Problema dos Caminhos Mínimos para instâncias com ciclos

negativos é NP-DIFÍCIL.

I Acreditamos que NÃO existem algoritmos eficientes para

resolver problemas NP-difíceis.

I Assim, vamos nos restringir ao Problema de Caminhos

Mínimos SEM CICLOS NEGATIVOS.

I Um algoritmo que resolve o problema restrito é o algoritmo de

Bellman-Ford, que também é baseado em relaxação.
 Algoritmo de Bellman-Ford

Definição do problema

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

Saída: FALSE, se existe um ciclo negativo atingível a partir de s.

Caso contrário, além de TRUE, também devolve um vetor d com
d[v] = dist(s,v) para v ∈ V e um vetor π definindo uma ÁRVORE
DE CAMINHOS MÍNIMOS.
 Algoritmo de Bellman-Ford

Ideia do algoritmo de Bellman-Ford

Relaxamento de caminho: Para QUALQUER caminho mínimo

(v0 , v1 , . . . , vk ), queremos relaxar (v0 , v1 ), (v1 , v2 ), . . . , (vk−1 , vk ) em ordem.

1. Executamos Relax para todas as arestas:

⇒ (v0 , v1 ) relaxada.
2. Executamos novamente Relax para todas as arestas:
⇒ (v0 , v1 ), (v1 , v2 ) relaxadas em ordem.
3. Executamos novamente Relax para todas as arestas:
⇒ (v0 , v1 ), (v1 , v2 ), (v2 , v3 ) relaxadas em ordem.
4. Repetimos esse passo até |V | − 1 vezes. Por quê?
⇒ (v0 , v1 ), (v1 , v2 ), . . . , (vk−1 , vk ) relaxadas em ordem.

Podemos verificar se o grafo contém CICLOS NEGATIVOS executando mais

uma vez:
I Se algum valor d[v] diminuir, então há ciclo negativo.
 Algoritmo de Bellman-Ford

Exemplo

5 −4
a −2 e
66

b 8 −3
−3 7

77
c d
9

a b c d e
d ∞
6 0 ∞
2 ∞
2 ∞
7 −2 4

Ordem: (a,c),(a,d),(a,e),(c,d),(c,e),(d,b),(d,e),(e,a),(b,a),(b,c).
 Algoritmo de Bellman-Ford

O algoritmo de Bellman-Ford

Algoritmo: Bellman-Ford(G, w , s)
1 Initialize-Single-Source(G, s)
2 para i ← 1 até |V [G]| − 1
3 para cada (u, v ) ∈ E [G]
4 Relax(u, v , w )

5 para cada (u, v ) ∈ E [G]

6 se d[v ] > d[u] + w (u, v )
7 devolva FALSE

8 devolva TRUE, d, π

Complexidade de tempo: O(VE )

 Algoritmo de Bellman-Ford

Correção do algoritmo Bellman-Ford

Teorema
Bellman-Ford devolve:

I FALSE, se existe um ciclo negativo atingível a partir de s.

I TRUE, caso contrário; neste caso devolve também:

I Um vetor d com d[v] = dist(s,v) para v ∈ V.

I Um vetor π definindo uma ÁRVORE DE CAMINHOS

MÍNIMOS.
 Algoritmo de Bellman-Ford

Correção do algoritmo Bellman-Ford

Primeiro, suponha que não há ciclos negativos atingíveis por s.

Considere v ∈ V[G] e os valores de d e π após o primeiro laço:

I Se v não é atingível, d[v] = ∞ (por Inexistência de caminho).

I Senão, existe caminho mínimo (v0 , v1 , . . . , vk ) de s = v0 a v = vk .

I Como k ≤ |V | − 1, então (v0 , v1 ), (v1 , v2 ), . . . , (vk−1 , vk ) foram

relaxadas NESTA ORDEM.
I Por Relaxamento de caminho, d[v] = dist(s,v).

I Também, por Sugrafo de predecessores: π induz um caminho

mínimo de s a v.
 Algoritmo de Bellman-Ford

Correção do algoritmo Bellman-Ford

Também temos que mostrar que nesse caso Bellman-Ford

devolve TRUE.

I Considere d imediatamente após o primeiro laço.

I Nesse instante, d[v] = dist(s,v) para todo vértice v.

I Por Convergência, sabemos que d nunca mais muda.

I Portanto, o teste da linha 6 falha sempre.

I Concluindo que o algoritmo devolve TRUE.

 Algoritmo de Bellman-Ford

Correção do algoritmo Bellman-Ford

Suponha agora que (G, w ) contenha CICLO NEGATIVO

alcançável por s.

Queremos mostrar que o algoritmo devolve FALSE:

I Seja C = (v0 , v1 , . . . , vk = v0 ) um ciclo tal que

w (C ) = ki=1 w (vi−1 , vi ) < 0.

P

I Suponha, por contradição que o algoritmo devolve TRUE.

I Como relaxamos cada aresta (vi−1 , vi ):

d[vi ] ≤ d[vi−1 ] + w (vi−1 , vi ).

 Algoritmo de Bellman-Ford

Correção do algoritmo Bellman-Ford

I Somando as desigualdades anteriores para cada aresta do ciclo,

temos:
k
X k
X
d[vi ] ≤ (d[vi−1 ] + w (vi−1 , vi ))
i=1 i=1
k
X k
X
= d[vi−1 ] + w (vi−1 , vi ).
i=1 i=1

Pk Pk
I Como v0 = vk , temos que i=1 d[vi ] = i=1 d[vi−1 ].
Pk
I Logo, 0 ≤ i=1 w (vi−1 , vi ) = w (C ).
I Mas isso é uma contradição, pois C é ciclo negativo.

I Concluindo que, nesse caso, o algoritmo devolve FALSE.

 Sistemas de
restrições de
diferenças
 Sistemas de restrições de diferenças

Exemplo
Uma aplicação de caminhos mínimos é encontrar x1 , x2 , . . . , xn que
satisfaçam:
x1 − x2 ≤ 0
x1 − x5 ≤ −1
x2 − x5 ≤ 1
x3 − x1 ≤ 5
x4 − x1 ≤ 4
x4 − x3 ≤ −1
x5 − x3 ≤ −3
x5 − x4 ≤ −3

Onde:
I xi representa a hora do evento i
I xj − xi ≤ bk significa que deve haver um intervalo de pelo menos bk
horas entre eventos i e j
 Sistemas de restrições de diferenças

Exemplo

Podemos reescrever as restrições de forma matricial:

1 −1
   
0 0 0 0
 1
 0 0 0 −1  
 x1
 
 −1 

 0
 1 0 0 −1 
  x2 

 1 

 −1 0 1 0 0     5 
   x3  ≤  
 −1 0 0 1 0 
   4 
  x4   
 0
 0 −1 1 0  x5

 −1 

 0 0 −1 0 1   −3 
0 0 0 −1 1 −3

Algumas soluções:
I x = (−5, −3, 0, −1, −4),
I x 0 = (0, 2, 5, 4, 1),. . .
 Sistemas de restrições de diferenças

Soluções de sistemas de restrições de diferenças

Lema
Seja x = (x1 , . . . , xn ) uma solução de um sistema de restrições de
diferença Ax ≤ b e d uma constante. Então

x + d = (x1 + d, . . . , xn + d)

também é uma solução de Ax ≤ b.

Mostraremos a seguir como encontrar uma solução de um sistema

Ax ≤ b de restrições de diferença resolvendo um problema de
caminhos mínimos.
 Sistemas de restrições de diferenças

Grafo de restrições

Construímos o chamado GRAFO DE RESTRIÇÕES fazendo o

seguinte:

1. Primeiro criamos um grafo em que:

I Cada vértice vi corresponde a uma variável xi .

I Cada aresta (vi , vj ) tem peso bk e corresponde a uma restrição

xj − xi ≤ bk .
I Logo, a matriz A do sistema de restrições corresponde à
transposta matriz de incidência desse grafo obtido

2. Finalmente, adicionamos um vértice especial v0 e uma aresta

de v0 a cada outro vértice vi com peso 0.
 Sistemas de restrições de diferenças

Grafo de restrições

Formalmente, dado o sistema Ax ≤ b de restrições de diferença,

construímos o grafo G = (V, E) tal que:

I V = {v0 , v1 , . . . , vn }.

I E = {(v0 , v1 ), . . . , (v0 , vn )} ∪ {(vi , vj ) : xj − xi ≤ bk é restrição}

E associamos pesos:
(
bk se xj − xi ≤ bk é restrição
I w (vi , vj ) =
0 se i = 0
 Sistemas de restrições de diferenças

Grafo de restrições

v1

0 −1 0

0 1
v0 v5 v2
4 5
0
−3
−3 −3

−1
v4 v3
0

Uma solução viável é x = (−5, −3, 0, −1, −4).

 Sistemas de restrições de diferenças

Grafo de restrições

Teorema
Seja Ax ≤ b um sistema de restrições de diferença e G = (V, E) o
grafo de restrições associado. Então:
I Se G não contém ciclos negativos,

x = (dist(v0 , v1 ), dist(v0 , v2 ), . . . , dist(v0 , vn ))

é uma solução viável do sistema.

I Se G contém ciclos negativos, o sistema não possui solução.
viável.
 Sistemas de restrições de diferenças

Resolvendo um sistema de restrições de diferença

Para RESOLVER O SISTEMA, basta resolver caminhos mínimos:

I Executamo Bellman-Ford a partir de v0 no grafo de
restrições G.
I Como todo vértice é atingível de v0 , se houver ciclo negativo,
o algoritmo devolve FALSE.
I Se não existir ciclo negativo, então obtemos a solução
x = (d[v1 ], d[v2 ], . . . , d[vn ]).
O TEMPO DE EXECUÇÃO é calculado como segue:
I A matriz A tem dimensões m × n.
I Então, G possui n + 1 vértices e n + m arestas.
I Logo, o tempo de execução de Bellman-Ford em G é
O((n + 1)(n + m)) = O(n2 + nm).
Algoritmo de
Bellman-Ford MC558 - Projeto e Análise de
Algoritmos II

13
09/24

Santiago Valdés Ravelo

[Link]
ravelo@[Link]