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
