PUERTA | PUERTA-CS-2009 | Pregunta 12

¿Cuál de las siguientes afirmaciones es correcta con respecto al algoritmo de ruta más corta de Bellman-Ford?

P: Always finds a negative weighted cycle, if one exist s.
Q: Finds whether any negative weighted cycle is reachable 
   from the source. 

(A) Solo P
(B) Solo Q
(C) Tanto P como Q
(D) Ni P ni Q

Respuesta: (B)
Explicación: el algoritmo de ruta más corta de Bellman-Ford es un algoritmo de ruta más corta de fuente única. Por lo tanto, solo puede encontrar ciclos a los que se pueda acceder desde una fuente determinada, no cualquier ciclo de peso negativo. Considere una desconexión donde un ciclo de peso negativo no es accesible desde la fuente en absoluto.

Si hay un ciclo de peso negativo, aparecerá en la ruta más corta, ya que el ciclo de peso negativo siempre formará una ruta más corta cuando se itera a través del ciclo una y otra vez.
Cuestionario de esta pregunta