Algoritmos | Graficar las rutas más cortas | Pregunta 8

En un gráfico ponderado, suponga que la ruta más corta desde un origen ‘s’ hasta un destino ‘t’ se calcula correctamente utilizando un algoritmo de ruta más corta. ¿Es verdadera la siguiente afirmación?
Si aumentamos el peso de cada borde en 1, el camino más corto siempre permanece igual.
(A) Sí
(B) No

Respuesta: (B)
Explicación: Véase el siguiente contraejemplo.

Hay 4 aristas sa, ab, bt y st de pesos 1, 1, 1 y 4 respectivamente. El camino más corto de s a t es sa, ab, bt. SI aumentamos el peso de cada borde en 1, el camino más corto cambia a st.

   1      1     1
s-----a-----b-----t
 \              /
   \          /
     \______/
        4

Cuestionario de esta pregunta