← Volver a los ejercicios

Problemas

Antes de escribir código hay que reconocer el problema. Cada escenario está en palabras: hay que decir si pide los caminos más cortos desde un origen (SSSP) o entre todos los pares (APSP), y cuál de los algoritmos de la lista conviene: la amplitud, los caminos en un grafo acíclico, Dijkstra, Bellman-Ford-Moore, Floyd-Warshall o repetir n veces un algoritmo de SSSP. Lo que decide es lo que dice el texto: si hay pesos y de qué signo, si hay ciclos, cuántos orígenes se piden y qué tan denso es el grafo. Cada respuesta equivocada explica qué falla o qué costo no conviene.

1. El escenario

Escenario . .

2. La versión y el algoritmo

3. Para llevarse

Sin solución aquí. Tome el escenario del metro y cámbielo de tres maneras: que los tramos tengan duraciones distintas, que algunos tramos devuelvan tiempo, y que además se pidan los tiempos entre todas las parejas de estaciones. Diga en cada caso qué algoritmo escogería y cuánto cuesta.