RE: Comentarios Anonimos (MAC0328)

[Jose Coelho de Pina <coelho@linux.ime.usp.br>]

anonymous@ime.usp.br writes:
 > seria possível especificar o que exatamente deve ser
 > feito no ep 4? Acho que com tanta teoria junto do
 > enunciado ficou um pouco vago o que realmente deve ser
 > implementado.
 >

Não sei se ajuda, mas ai vai:

   (1) Leia a introdução abaixo;
   (2) Implemente o pseudo-código abaixo;
   (3) Acrescente a sua implementação a detecção de ciclos
       negativos, que também está abaixo;
   (4) Leia a seção "comportamento do seu programa" para ver como o 
       seu programa deve se comunicar com um possível usuário. 

--------------------------------------------------------------------
Introdução 

Este exercício-programa consiste na implementação do algoritmo de
Bellman-Ford-Moore que recebe um grafo g com comprimentos nos arcos e um
vértice r e devolve um ciclo negativo acessível a partir de r ou um
passeio de comprimento mínimo de r a v, para cada vértice v do grafo.

[...]

            BELLMAN-FORD-MOORE (Grafo g, Vértice r)
              para cada vértice v de g faça
                  estado[v] := NÃO-VISTO
                  dist[v] := INFINITO
                  pred[v] := NULL
              estado[r] := VISITADO
              dist[r] := 0
              Q := INICIALIZA-FILA(r)
              enquanto Q não está vazia faça
                  u := PRIMEIRO-DA-FILA(Q)
                  para cada uv em Adj[u] faça
                      se dist[u] + len(u,v) < dist[v] então
                        estado[v] := VISITADO
                        dist[v] := dist[u]+len(u,v)
                        pred[v] := u
                        se v não está em Q então 
                          INSIRA-NA-FILA(Q,v)
                  estado[u] := EXAMINADO
              devolva dist e pred

[...]
Ciclos negativos 

Para transforma o método de Bellman-Ford-Moore acima em um algoritmo
deve-se fazer com que ele pare mesmo na presença de ciclos
negativos. Uma maneira fácil de fazer isto é contar o número de passos
executados. Inclua duas variáveis ao método, um inteiro passo e uma
váriavel último indicando o último vértice que foi examinado durante o
presente passo do método. Inicialmente passo = 0 e último = r. Depois
que o vértice último é examinado incrementa-se de 1 a variável passo e
último passa a ser o último vértice da fila Q. Se passo recebe o valor n
com a fila Q não vazia, o (agora) algoritmo deve parar e anunciar a
presença de um ciclo negativo no grafo.

Usando o lema a seguir pode-se localizar um ciclo negativo, caso um tal
ciclo exista. Se v é um vértice, então

      pred1[v] = pred[v] 
      pred2[v] = pred[pred[v]] 
      pred3[v] = pred[pred[pred[v]]] 
      [...] 

e assim por diante. 

Lema 4. Se a fila Q não está vazia no final do passo n-1 então predk[v]
= v para algum vértice v e inteiro k e o correspondente ciclo em g é
negativo.
-------------------------------------------------------------------------