Dado un gráfico dirigido donde el peso de cada borde es el mismo, ¿podemos encontrar de manera eficiente el camino más corto desde una fuente determinada hasta el destino usando? (A) Recorrido primero en anchura (B) Algoritmo de ruta más corta de Dijkstra (C) No se puede usar ni Recorrido primero en anchura ni el … Continue reading «Algoritmos | Graficar las rutas más cortas | Pregunta 11»
¿Es válida la siguiente afirmación?. Dado un gráfico ponderado donde los pesos de todos los bordes son únicos (no hay dos bordes que tengan los mismos pesos), siempre hay una ruta más corta única desde un origen hasta un destino en dicho gráfico. (A) Verdadero (B) Falso Respuesta: (B) Explicación: Puede haber más de un … Continue reading «Algoritmos | Graficar las rutas más cortas | Pregunta 14»
¿Es válida la siguiente afirmación?. Dado un gráfico donde todos los bordes tienen pesos positivos, las rutas más cortas producidas por el algoritmo de Dijsktra y Bellman Ford pueden ser diferentes, pero el peso de la ruta siempre será el mismo. (A) Verdadero (B) Falso Respuesta: (A) Explicación: Dijkstra y Bellman-Ford funcionan bien para un … Continue reading «Algoritmos | Graficar las rutas más cortas | Pregunta 15»
¿Es válida la siguiente afirmación sobre los caminos más cortos? Dado un gráfico, supongamos que hemos calculado el camino más corto desde una fuente a todos los demás vértices. Si modificamos el gráfico de modo que los pesos de todos los bordes se conviertan en el doble del peso original, entonces el camino más corto … Continue reading «Algoritmos | Graficar las rutas más cortas | Pregunta 12»