Skip to the content
Start

Project: the shortest route

Python · Unit 24: Data structures

You have the map of a small subway: each station with the list of the stations it reaches directly, in alphabetical order.

You're going to answer two questions: how many hops away the destination is, and which way to go. Both are walked breadth-first, with the queue of what's pending, the dictionary of neighbors and the set of what's been seen.

links = {"south": ["center"],
         "center": ["north", "south"],
         "north": ["center"]}
print(links["center"])
print("north" in links["south"])

Prints

['north', 'south']
False

The rest of the explanation is in the lesson, which is part of the full plan.

Exercises in this lesson

You do them in the app, which checks them on the spot and explains why.

  1. 1. Write the code

    Write steps(links, start, end): it returns how many hops the shortest route from start to end has, or -1 if there's no way to get there. In the queue you can line up (station, hops) pairs, like the heap's tuples.

  2. 2. Complete the code

    Leave the route from the start to the end. It should print: ['south', 'center', 'north']

  3. 3. Write the code

    Write short_route(links, start, end): it returns the list of stations from the start to the end along the shortest route, or [] if there's no way to get there. You already have build, which flips what you kept in parent. If two routes tie in length, the winner is the one that comes first alphabetically at the first station where they differ: the neighbors come in that order, so it's enough to keep the first time you reach each station.

Do this lesson

It opens in your browser. This lesson is part of the full plan; the first unit of each course is free.

See all lessons →