Considere las siguientes afirmaciones sobre el algoritmo de Ford de Bellman para encontrar el camino más corto en un grafo conectado dirigido G que tiene pesos de borde integrales.
Declaración I: Siempre descubrirá el ciclo de peso de borde negativo en G accesible desde la fuente.
Declaración II: Siempre dará la respuesta correcta para el gráfico G.
Elija entre las opciones que se dan a continuación.
(A) Ambas afirmaciones son verdaderas
(B) Ambas afirmaciones son falsas
(C) El enunciado I es verdadero y el enunciado II es falso
(D) El enunciado II es verdadero y el enunciado I es falso
Respuesta: (C)
Explicación: el enunciado 1 es verdadero como en la iteración n de Bellman Ford, si la longitud del camino de cualquier Node accesible desde la fuente se reduce, lo que significa que tenemos un ciclo de peso de borde negativo en el gráfico.
La declaración 2 es falsa ya que ningún algoritmo puede dar la respuesta correcta si el gráfico tiene un ciclo de peso de borde negativo.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA