Considere las siguientes declaraciones:
I. Dado un gráfico G = (V, E) con distintos pesos de borde positivos, el algoritmo de Bellman-Ford y el algoritmo de Dijkstra pueden producir diferentes árboles de ruta más corta a pesar de producir siempre los mismos pesos de ruta más corta.
II. Dado un gráfico G = (V, E) con distintos pesos de borde positivos, el algoritmo de Kruskal y el algoritmo de Prim pueden producir diferentes árboles de expansión a pesar de producir siempre los mismos pesos mínimos.
¿Cuál de las siguientes opciones es la correcta?
(A) Sólo la afirmación I es correcta.
(B) Sólo la afirmación II es correcta.
(C) Ambas afirmaciones I y II son correctas.
(D) Ni la afirmación I ni la II son correctas.
Respuesta: (A)
Explicación: La afirmación (I) es correcta.
Se garantiza que ambos algoritmos producirán el mismo peso de ruta más corta, pero si hay varias rutas más cortas, Dijkstra elegirá la ruta más corta de acuerdo con la estrategia codiciosa, y Bellman-Ford elegirá la ruta más corta según el orden de las relajaciones, y los dos los árboles de ruta más corta pueden ser diferentes.
Pero la afirmación (II) no es correcta, ya que la extensión mínima siempre es única en un gráfico G = (V, E) con distintos pesos de borde positivos.
La opción (A) es correcta.
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