RE: Comentarios Anonimos (MAC0328)

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

anonymous@ime.usp.br writes:
 >     Como eu faço pra calcular o INFINITO? Precisaria
 >     saber todos as distancias dos arcos??


Sim, para calcular INFINTO precisar olhar o comprimento de
cada arco, pegar o maior, mutiplicar pelo número de vértice
e somar 1.

Agora, mudando de assunto, notem que a implementação do
algoritmo de Bellman-Ford não precisa desse tal infinito.
Pode-se utilizar o campo pred de cada vértice para
identificarmos se ele já foi ou não alcançado por um caminho
a partir da raiz, certo?! coisa do tipo

  if (v->pred == NULL) {...}

é equivalente a

  if (v->dist == INFINITO) {...}

Se os campos dist dos vértices não forem inicializados 
é necessário tomar o cuidade com o uso desse campo.
Só podemos fazer

  if (v->dist > u->dist + a->len) {...}

quando, a priori, sabemos que

  v->pred != NULL


coelho