Saltar al contenido
Empezar

Proyecto: la ruta más corta

Python · Unidad 24: Estructuras de datos

Tienes el mapa de un metro chico: cada estación con la lista de las estaciones a las que llega directo, en orden alfabético.

Vas a contestar dos preguntas: a cuántos tramos está el destino y por dónde se va. Las dos se recorren a lo ancho, con la cola de pendientes, el diccionario de vecinos y el conjunto de vistos.

mapa = {"sur": ["centro"],
        "centro": ["norte", "sur"],
        "norte": ["centro"]}
print(mapa["centro"])
print("norte" in mapa["sur"])

Imprime

['norte', 'sur']
False

El resto de la explicación está en la lección, que es del plan completo.

Ejercicios de esta lección

Se hacen en la app, que los corrige al momento y explica por qué.

  1. 1. Escribe el código

    Escribe pasos(mapa, inicio, fin): regresa cuántos tramos tiene la ruta más corta de inicio a fin, o -1 si no hay forma de llegar. En la cola puedes formar pares (estacion, tramos), como las tuplas del montículo.

  2. 2. Completa el código

    Deja la ruta del inicio al fin. Debe imprimir: ['sur', 'centro', 'norte']

  3. 3. Escribe el código

    Escribe ruta_corta(mapa, inicio, fin): regresa la lista de estaciones del inicio al fin por la ruta más corta, o [] si no hay forma de llegar. Ya tienes arma, que voltea lo que guardaste en padre. Si dos rutas empatan en largo, gana la que en la primera estación distinta va antes en orden alfabético: los vecinos vienen en ese orden, así que basta quedarte con la primera vez que llegas a cada estación.

Hacer esta lección

Se abre en el navegador. Esta lección es del plan completo; la primera unidad de cada curso es gratis.

Ver todas las lecciones →