Skip to main content

Algorithms

Recover the route from a breadth-first search

Build a route finder that remembers each transfer, handles a cycle, and distinguishes staying put from an unreachable stop.

Try the 5-minute exercise

A visitor at Gate asks how to reach the Lab using the fewest shuttle legs. “Two legs” is a distance. The visitor still needs to know where to change. Keep one extra fact when a stop first joins the search queue: the stop that led you there.

Trace the first transfer

From Gate, the timetable lists Cafe before Hall. Both have a direct shuttle to Lab. When Cafe comes off the queue it discovers Lab and records Cafe as its parent. When Hall comes off the queue, Lab already has a parent. Reading backward now gives Lab, Cafe, Gate. Turn that sequence around to give the visitor directions.

from collections import deque

def route(roads, start, end):
    # The caller supplies known stops; roads lists outgoing links.
    parent = {start: None}
    queue = deque([start])
    while queue:
        stop = queue.popleft()
        if stop == end:
            path = []
            while stop is not None:
                path.append(stop)
                stop = parent[stop]
            return path[::-1]
        for neighbor in roads.get(stop, []):
            if neighbor not in parent:
                parent[neighbor] = stop
                queue.append(neighbor)
    return None

roads = {"Gate": ["Cafe", "Hall"], "Cafe": ["Gate", "Lab"],
         "Hall": ["Lab"], "Lab": [], "Depot": []}
assert route(roads, "Gate", "Lab") == ["Gate", "Cafe", "Lab"]
assert route(roads, "Gate", "Gate") == ["Gate"]
assert route(roads, "Gate", "Depot") is None

Test what the traveler was promised

Swap Cafe and Hall in Gate’s list. The returned transfer changes to Hall and the trip still takes two legs. When order is unspecified, a test for this graph can check the endpoints, verify that each consecutive pair is a real directed edge, and assert a length of two edges. Requiring Cafe would unnecessarily tie the test to one timetable order.

The return trip also deserves a test. Lab has no outgoing shuttles in this timetable, so reversing the outward directions would give the visitor a trip they cannot make. Finally, this search treats each shuttle leg as one step. A direct shuttle taking an hour beats two ten-minute legs under that rule. Ask whether the traveler cares about transfers or elapsed time before choosing the algorithm. Python deque reference

Put it into practice · 5 minutes

Recover a route from breadcrumbs

Try the exercise and get feedback on your answer.

Try the exercise