Considere un gráfico no dirigido ponderado con pesos de borde positivos y sea uv un borde en el gráfico. Se sabe que el camino más corto desde el vértice fuente s hasta u tiene un peso de 53 y el camino más corto desde s hasta v tiene un peso de 65. ¿Cuál de las siguientes afirmaciones es siempre verdadera?
(A) peso (u, v) < 12
(B) peso (u, v) ≤ 12
(C) peso (u, v) > 12
(D) peso (u, v) ≥ 12
Respuesta: (D)
Explicación : 
El peso mínimo ocurre cuando (S,U) + (U,V) = (S,V)
De lo contrario (S,U) + (U,V) >= (S,V)
Dado (S,U) = 53, (S,V) = 65
53 + (U,V) >= 63
(U,V) >= 12.
Esta solución es aportada por Anil Saikrishna Devarasetty
Cuestionario de esta pregunta
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