Ata de Exercícios
Caminhos Mais Curtos de Todos os Pares
06/06/2003

25.1-9

Modifique FASTER-ALL-PAIRS-SHORTEST-PATHS de modo que ele possa detectar a presença de um ciclo de peso negativo.

Algoritmo original:

FASTER-ALL-PAIRS-SHORTEST-PATH(W)
1  n ← linhas[W]
2  L(1) ← W
3  m ← 1
4  while m < (n - 1) do
5      L(2m) ← EXTEND-SHORTEST-PATHS(L(m), L(m))
6      m ← 2m
7  return L(m)

Foram consideradas duas estratégias para a resolução deste exercício, apresentadas abaixo.

25.1-9: Estratégia 1

Depois de terminarem as iterações do algoritmo, executar uma nova iteração de EXTEND-SHORTEST-PATHS. Se algum valor na matriz foi alterado, isto significa que há pelo menos um ciclo de peso negativo. Esta alteração está descrita no pseudocódigo abaixo, linhas 7-11.

FASTER-ALL-PAIRS-SHORTEST-PATH_1(W)
  1  n ← linhas[W]
  2  L(1) ← W
  3  m ← 1
  4  while m < (n - 1) do
  5      L(2m) ← EXTEND-SHORTEST-PATHS(L(m), L(m))
  6      m ← 2m
  7  matrizCiclo ← EXTEND-SHORTEST-PATHS(L(m), L(m))
  8  for i ← 1 to n do
  9      for j ← 1 to n do
10          if Lij(m) ≠ matrizCicloij then
11              error "Há ciclos negativos: impossível verificar os caminhos mais curtos de todos os pares."
12  return L(m)

25.1-9: Estratégia 2

Depois de terminarem as iterações do algoritmo, verificar se há algum valor negativo na diagonal principal. Se não houver ciclos negativos, todos os valores da diagonal devem ter o valor zero. Se houver ciclos negativos, haverá pelo menos um valor negativo na diagonal principal. Esta alteração está descrita no pseudocódigo abaixo, linhas 7-9.

FASTER-ALL-PAIRS-SHORTEST-PATH_2(W)
  1  n ← linhas[W]
  2  L(1) ← W
  3  m ← 1
  4  while m < (n - 1) do
  5      L(2m) ← EXTEND-SHORTEST-PATHS(L(m), L(m))
  6      m ← 2m
  7  for i ← 1 to n do
  8     if Lii(m) ≠ 0 then
  9          error "Há ciclos negativos: impossível verificar os caminhos mais curtos de todos os pares."
10  return L(m)

25.2-4

Como foi apresentado, o algoritmo de Floyd-Warshall exige o espaço Θ(n³), pois calculamos d_ij^(k) para i,j,k = 1, 2, ..., n. Mostre que o procedimento a seguir, que simplesmente retira todos os sobrescritos, é correto e, desse modo, apenas o espaço Θ(n²) é necessário.

O algoritmo modificado (FLOYD-WARSHALL') poderia não funcionar já que, por estar usando uma única matriz (no lugar de n matrizes, uma para cada valor de k, 1 ≤ k ≤ n), algum valor poderia ser sobrescrito de forma indevida. A prova de correção do algoritmo equivale, portanto, a provar que o algoritmo nunca sobrescreve um valor indevidamente.

Em primeiro lugar, é preciso definir o que é sobrescrita indevida. É necessário preocupar-se apenas com um valor fixo para k, já que as escritas (atribuições a elementos das matrizes D) ocorrem em "lotes", cada lote com um valor fixo para k. Estas alterações dependem apenas de valores da matriz D anterior (k - 1), que não é alterada, e da matriz D atual.. Então, sobrescrita indevida ocorreria se, para um determinado valor de k, elementos na matriz D^(k) fossem alterados para algum valor e, mais tarde, fosse necessário ler o valor que havia antes da alteração.

A linha 6 do algoritmo original pode ser definida da seguinte forma:

(1) a alteração de d_ij^(k) depende de d_ik^(k-1) , d_kj^(k-1)

Conseqüentemente,

(2) d_ik^(k) depende de d_ik^(k-1) e d_kk^(k-1)     (quando j = k)

(3) d_kj^(k) depende de d_kk^(k-1) e d_kj^(k-1)     (quando i = k)

Como a diagonal de toda matriz D é sempre zero (considerando-se que não existem ciclos negativos), as sentenças (2) e (3) podem ser reescritas da seguinte forma:

(4) d_ik^(k) depende de d_ik^(k-1)     (pois d_kk^(k-1) = 0)

(5) d_kj^(k) depende de d_kj^(k-1)     (pois d_kk^(k-1) = 0)

Ou seja, em cada iteração do for da linha 3, os elementos d_ik e d_kj não são alterados para o valor de k naquela iteração.

A sentença (1) pode ser reescrita da seguinte forma:

(6) a alteração de d_ij^(k) depende de d_ik^(k), d_kj^(k)

Portanto, para um dado valor de k:

1. elementos que estejam na linha k ou na coluna k não são alterados
2. elementos que estejam em linhas diferentes de k e colunas diferentes de k podem ser alterados. Esta alteração depende de elementos que estejam na linha k ou na coluna k.

Isto significa que, para cada iteração do for da linha 3, a única alteração ocorre em elementos que não estejam nem na linha k e nem na coluna k. Além disso, qualquer alteração se deve apenas a elementos que estejam na linha k ou na coluna k. Logo, nenhum elemento é sobrescrito de forma indevida, o que prova a correção do algoritmo FLOYD-WARSHALL'.

25.3-3

Suponha que w(u,v) ≥ 0 para todas as arestas (u,v) ∈ E. Qual é o relacionamento entre as funções peso w e ŵ?

Ambas as funções têm o mesmo valor. A técnica de reponderação de pesos do algoritmo de Johnson funciona da seguinte forma: acrescenta-se um vértice s ao grafo tal que existe uma aresta com peso zero que vai de s a todo vértice do grafo. A função h : V → R, que mapeia os vértices para números reais, é definida como a menor distância entre s e todo vértice do grafo. Como todo peso de aresta é positivo, a menor distância entre s e qualquer vértice é zero.

A função ŵ é definida da seguinte forma:

(1) ŵ(u,v) = w(u,v) + h(u) - h(v)

Como a função h tem valor zero para qualquer vértice do grafo, tem-se:

(2) ŵ(u,v) = w(u,v)    (pois h(u) e h(v) têm valor zero).