RE: bellman-ford vs bellman-ford-moor

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

Salve,

Eu havia enviado a resposta (um tanto quanto diferente) 
só para o André.
 
André T. Kowaltowski writes:
 > qual a diferença entre os algoritmos de bellman-ford e bellman-ford-moore. No
 > clrs o primeiro é apresentado como sendo O(nm), mas a descrição de uso é muito
 > similar ao bellman-ford-moore que, como vimos em sala, é O(n²+nm).

São o mesmo algoritmo. Algumas pessoas gostam de também dar
crédito ao Moore já que ele e o Bellman tiveram a mesma idéia:

 " E.F. Moore e, independentemente, R.E. Bellman propuseram
 que os vértices com estado VISITADO fossem examinados de
 acordo com uma ordem de busca em largura (breadth-first
 order)..."

Agora, esse negócio do consumo de tempo acho que é porque
nós não estamos suponto que m = Omega(n). Acho que o
CLRS fazem está hipótese [o que é razoável para o problema].

Hmmmm, agora eu me lembrei que mesmo para a implementação
que vocês devem fazer o consumo de tempo é O(nm).  Cópiei o
trecho abaixo lá do enunciado do EP4:

 "Para analisar o desempenho deste método divide-se a sua
  execução em passos. O passo zero consiste do exame do
  vértice r. Para j > 0, o passo j consiste do exame de todos
  os vértices na fila ao final do passo j - 1. Cada passo pode
  ser executado em tempo O(n+m) pois durante cada passo cada
  vértice e cada arco é examinado no máximo uma vez. (Hmmm,
  esse O(n+m) pode ser trocado por O(m). Por quê?) 
  [...] "

té +,
coelho