Considere un gráfico donde todos los pesos de los bordes son positivos. Hemos calculado la ruta más corta utilizando el algoritmo de ruta más corta de Dijkstra y el peso total de la ruta más corta es W.
Considere a continuación dos afirmaciones sobre el camino más corto desde un origen hasta un destino.
i) Si se modifica el gráfico y todos los pesos de los bordes se multiplican por x, entonces el camino más corto sigue siendo el mismo y el peso del camino más corto se convierte en W*x (W multiplicado por x).
ii) Si se modifica el gráfico y se agrega x a todos los pesos de borde, entonces el camino más corto sigue siendo el mismo y el peso del camino más corto se convierte en W + n*x. Donde n es el número de aristas en el camino más corto.
(A) Solo (i) es siempre Verdadero
(B) Solo (ii) es siempre Verdadero
(C) Ambos son siempre verdaderos
(D) Ni (i) ni (ii) son siempre verdaderas
Respuesta: (A)
Explicación:
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