¿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»
¿Cuál de los siguientes algoritmos se puede usar para calcular eficientemente las rutas más cortas de fuente única en un gráfico acíclico dirigido? (A) Dijkstra (B) Bellman-Ford (C) Clasificación topológica (D) Componente fuertemente conectado Respuesta: (C) Explicación: Usando la clasificación topológica, podemos encontrar las rutas más cortas de fuente única en tiempo O(V+E), que es … Continue reading «Algoritmos | Graficar las rutas más cortas | Pregunta 10»
Supongamos que ejecutamos el algoritmo de ruta más corta de fuente única de Dijkstra en el siguiente gráfico dirigido ponderado por borde con el vértice P como fuente. ¿En qué orden se incluyen los Nodes en el conjunto de vértices para los cuales se finalizan las distancias de camino más cortas? (GATE CS 2004) (A) … Continue reading «Algoritmos | Graficar las rutas más cortas | Pregunta 14 – Part 1»
¿La siguiente afirmación es verdadera o falsa? If we make following changes to Dijkstra, then it can be used to find the longest simple path, assume that the graph is acyclic. 1) Initialize all distances as minus infinite instead of plus infinite. 2) Modify the relax condition in Dijkstra’s algorithm to update distance of an … Continue reading «Algoritmos | Graficar las rutas más cortas | Pregunta 9»
Para implementar el algoritmo de ruta más corta de Dijkstra en gráficos no ponderados para que se ejecute en tiempo lineal, la estructura de datos que se utilizará es: (A) Cola (B) Pila (C) Heap (D) B-Tree Respuesta: (A) Explicación: La ruta más corta en un gráfico no ponderado significa el menor número de aristas … Continue reading «Algoritmos | Graficar las rutas más cortas | Pregunta 2»
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) … Continue reading «Algoritmos | Graficar las rutas más cortas | Pregunta 8»